德州王霞网站建设,坦洲网站建设公司,室内装潢设计专业培训,市场调研报告范文大全文章目录 一、实验内容二、实验步骤三、分析说明#xff08;包括核心代码及解释#xff09;1. 随机生成N个二维坐标节点。2. 应用遗传算法并用选定的编程语言#xff08;C#xff09;#xff0c;设计简单的遗传优化系统对问题进行求解#xff0c;求出问题的最优解。选择算… 文章目录 一、实验内容二、实验步骤三、分析说明包括核心代码及解释1. 随机生成N个二维坐标节点。2. 应用遗传算法并用选定的编程语言C设计简单的遗传优化系统对问题进行求解求出问题的最优解。选择算法采用赌轮选择法交叉算法变异算法代码如下 3.选择适当可视化方法显示结果。4. 分析适应度函数对启发式搜索算法的影响。5. *扩展选做题考虑不同数值N对最终结果和求解性能的影响。对于比较大的N是否设计更快速的近似方法代替原有算法。 四、总结心得 一、实验内容
问题描述旅行商问题即TSP问题Traveling Salesman Problem又译为旅行推销员问题、货郎担问题是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市他必须选择所要走的路径路径的限制是每个城市只能拜访一次而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 内容提要以N个节点的TSP旅行商问题问题为例应用遗传算法并用选定的编程语言设计简单的遗传优化系统对问题进行求解求出问题的最优解通过实验培养学生利用遗传算法进行问题求解的基本技能。
二、实验步骤
随机生成N个二维坐标节点。应用遗传算法并用选定的编程语言我选择的语言是C设计简单的遗传优化系统对问题进行求解求出问题的最优解。选择适当可视化方法显示结果。分析适应度函数对启发式搜索算法的影响。*扩展选做题考虑不同数值N对最终结果和求解性能的影响。对于比较大的N是否设计更快速的近似方法代替原有算法。
三、分析说明包括核心代码及解释
1. 随机生成N个二维坐标节点。
2. 应用遗传算法并用选定的编程语言C设计简单的遗传优化系统对问题进行求解求出问题的最优解。
实际上遗传算法并不能百分百得到TSP问题的最优解但能够较好地近似求解TSP问题在问题规模比较大的时候遗传算法的优点能够明显体现出来但当规模非常大时遗传算法的效率也会变低。
利用遗传算法解决TSP问题的流程可以归为如下图 大致思路首先随机生成N个城市的二维坐标计算出两两城市之间的距离保存在一个二维数组中接着随机初始化种群为种群中的每一个个体随机生成一段城市访问序列计算初始种群中每个个体的适应度定义为城市序列中相邻两城的距离之和的倒数和生存被选择概率然后循环迭代对种群进行选择、交叉和变异操作这三步骤的实现后面详讲当迭代次数达到一定值时结束循环取循环过后的种群中适应度最高的作为TSP问题的最优解打印出初始种群的最优路线顺序以及迭代过后得到的种群的最优路线顺序并在Excel表中绘制两条路线进行对比。
选择算法采用赌轮选择法
求出当前种群每个个体的适应度后计算出种群所有个体的适应度之和个体适应度除以总适应度即为每个个体的的生存被选择概率计算出每个个体的累计概率随机生成一个0-1之间的随机浮点数根据这个浮点数所在的累计概率区间选择出对应的个体一轮过后未被选择到的个体就视为在自然选择中被淘汰的个体。当然也可能发生小概率事件当前最优的个体被淘汰了这也是遗传算法不能得到最优解的原因之一。
例种群中有5条路线每条路线的适应度分别为0.05、0.15、0.35、0.25和0.2累计概率为0.05、0.2、0.55、0.8和1那么随机数落在[0,0.05]区间则表示0号个体被选择落在[0.05,0.2]区间则表示1号个体被选择以此类推。可以用坐标轴形式展示如下图所示
交叉算法
因为选择的个体是按照依次生成随机数所在区间所决定的也就是说选择出来的个体的顺序是随机的即此时种群数组中的个体顺序是随机的。因此可以假设第kk0、2、4、…、2n个个体和k1个个体有一定概率我设置的Pc为0.9交叉变换这个概率就是交叉概率随机生成一个0-1之间的随机浮点数若这个数在交叉概率以内就将当前个体(第k个)与k1个个体进行交叉。
TSP问题中交叉算法最主要的是解决交叉后产生的基因冲突问题例如
解决的方案是用映射关系在两个个体交叉的那段中确定映射关系将非交叉段中存在映射关系的数字替换为其映射的数即可解决冲突问题
变异算法
设每个个体有一定概率变异概率Pm我设置的是0.1发生基因多次对换对种群中的每个个体生成一个0-1之间的随机数若该随机数在[0,Pm]内则认为该个体发生变异随机生成两个不相等的范围在[0,城市数 - 1]之间的随机整数将这个个体在这两个随机数下标对应的城市编号对换重复上述变换n次n取[1城市数]之间的随机整数。 当完成选择、交叉和变异后用得到的种群覆盖原来的种群判断迭代次数是否达到最大迭代次数若达到则输出当前种群的最优路线否则对新得到的一代种群重复进行上述选择、交叉和变异操作。
代码如下
#includeiostream
#includevector
#includeiomanip
#includeunordered_map
#includealgorithm
#includemath.h
#includetime.h#define GROUP_NUM 100 //种群规模
#define CITY_NUM 15 //城市数量
#define ITERATION_NUM 1000 //最大迭代次数
#define Pc 0.9 //交叉率
#define Pm 0.1 //变异率
using namespace std;//路线类
class Route{
public:vectorint seq; //路线的城市顺序double fitness; //适应度定义为城市序列中相邻两城的距离之和的倒数double Ps; //生存概率被选择概率double dis; //路线距离//构造函数Route() {seq vectorint(CITY_NUM 1);fitness 0;Ps 0;}
};//城市坐标类
class City{
public:int x; //横坐标int y; //纵坐标
};//为自定义类(Route)制定排序规则
//升序排列即生存概率高的排在后面
bool my_cmp(Route r1, Route r2) {return r1.Ps r2.Ps;
}//城市之间的距离矩阵
vectorvectordouble dis(CITY_NUM, vectordouble(CITY_NUM, 0.0));//种群
vectorRoute group(GROUP_NUM);//城市
vectorCity city(CITY_NUM);//城市初始化函数随机生成CITY_NUM个二维坐标节点计算城市间的距离并存在距离矩阵中
void city_init() {//设城市全部坐落在100 * 100的二维平面内//种下随机种子使每次运行生成的城市坐标不同srand((unsigned)time(NULL));cout 生成的随机城市坐标 endl;for(int i 0; i CITY_NUM; i) {//为每个城市随机生成坐标city[i].x rand() % 100;city[i].y rand() % 100;cout i 、 ( city[i].x , city[i].y ) endl;}//计算城市距离,城市i到城市j的距离与城市j到i的距离相等for(int i 0; i CITY_NUM; i) {for(int j i; j CITY_NUM; j) {int temp1 (city[i].x - city[j].x) * (city[i].x - city[j].x);int temp2 (city[i].y - city[j].y) * (city[i].y - city[j].y);dis[i][j] sqrt(temp1 temp2);dis[j][i] dis[i][j];}}
}//种群初始化函数,生成GROUP_NUM个初始随机访问城市序列
void group_init() {srand((unsigned)time(NULL));for(int i 0; i GROUP_NUM; i) {//用哈希表防止序列中生成重复的城市unordered_mapint, int mp;for(int j 0; j CITY_NUM; j) {int num rand() % CITY_NUM;//如果随机生成的数重复了则重新生成直到不重复为止while(mp[num] ! 0) {num rand() % CITY_NUM;}mp[num];group[i].seq[j] num;}group[i].seq[CITY_NUM] group[i].seq[0];}/*cout 初始种群 endl;for(int i 0; i GROUP_NUM; i) {for(int j 0; j CITY_NUM; j) {cout group[i].seq[j] ;}cout endl;}*/}//计算初始种群中每个个体的适应度及生存概率
//适应度设置为序列中相邻两城之间的距离之和的倒数
void cal_group() {//种群总适应度double total_fit 0.0;//计算每个个体的适应度for(int i 0; i GROUP_NUM; i) {double total_dis 0;for(int j 1; j CITY_NUM; j) {total_dis dis[group[i].seq[j]][group[i].seq[j - 1]];}group[i].dis total_dis;//个体的适应度为总距离的倒数group[i].fitness 1.0 / total_dis;//测试计算出来的路径和是否正确//cout total_dis group[i].fitness endl;total_fit group[i].fitness;}//计算每个个体的生存概率被选择概率,为个体适应度 / 总适应度for(int i 0; i GROUP_NUM; i) {group[i].Ps group[i].fitness / total_fit;}
}//打印种群信息
void show() {for(int i 0; i GROUP_NUM; i) {for(int j 0; j CITY_NUM; j) {cout group[i].seq[j] ;}cout setprecision(4) 适应度为 group[i].fitness 生存概率为 group[i].Ps endl;}
}//选择
void select() {//计算累计概率vectordouble acc_p(GROUP_NUM);acc_p[0] group[0].Ps;for(int i 1; i GROUP_NUM; i) {acc_p[i] acc_p[i - 1] group[i].Ps;}//记录被选择的个体利用赌轮选择法随机生成0~1之间一个数根据计算出来的累计概率选择个体vectorRoute sel_individual(GROUP_NUM);srand((unsigned)time(NULL));for(int i 0; i GROUP_NUM; i) {//生成0~1的随机数,4位小数float random rand() % (10000) / (float)(10000);//cout random ;for(int j 0; j acc_p.size(); j) {if(random acc_p[j]) {//cout random acc_p[j] endl;sel_individual[i] group[j];break;}}}//被选择的种群覆盖初始种群for(int i 0; i GROUP_NUM; i) {group[i] sel_individual[i];}/*cout 打印经过自然选择后的种群序列 endl;for(int i 0; i GROUP_NUM; i) {cout i 、 ;for(int j 0; j CITY_NUM; j) {cout group[i].seq[j] ;}cout 适应度为 group[i].fitness 生存概率为 group[i].Ps endl;}*/
}//交叉交配算法
//第kk0、2、4、...、2n个个体和k1个个体有一定的概率交叉变换
//设置一个0~1之间的随机数若在Pc交配率范围内则该该个体k与下一个个体k1进行交配
void mating() {//随机生成子代交配时DNA交换的数量(1~CITY_NUM / 2)srand((unsigned)time(NULL));int change_num (rand() % CITY_NUM / 2) 1;//cout 交换DNA数量 change_num endl;//开始交配for(int i 0; i CITY_NUM; i 2) {//生成0-1之间的随机数(3位小数)float random rand() % (1000) / (float)(1000);//在交配率以内则该个体i与下一个个体i1进行交配if(random Pc) {//随机生成交配点int point rand() % (CITY_NUM - change_num);//cout i 与 i 1 进行交配断点 point endl;//先将双亲的交配片段进行互换并用哈希映射记录然后解决基因冲突unordered_mapint, int hash1;for(int j point; j change_num point; j) {int a group[i].seq[j];int b group[i 1].seq[j];if(hash1.find(a) ! hash1.end()) {a hash1[a];}if(hash1.find(b) ! hash1.end()) {b hash1[b];}hash1[a] b;hash1[b] a;swap(group[i].seq[j], group[i 1].seq[j]);}//处理双亲交配后可能产生的基因冲突问题(断点前)for(int j 0; j point; j) {if(hash1.find(group[i].seq[j]) ! hash1.end()) {group[i].seq[j] hash1[group[i].seq[j]];}if(hash1.find(group[i 1].seq[j]) ! hash1.end()) {group[i 1].seq[j] hash1[group[i 1].seq[j]];}}//断点后for(int j point change_num; j CITY_NUM; j) {if(hash1.find(group[i].seq[j]) ! hash1.end()) {group[i].seq[j] hash1[group[i].seq[j]];}if(hash1.find(group[i 1].seq[j]) ! hash1.end()) {group[i 1].seq[j] hash1[group[i 1].seq[j]];}}}//最后一个城市的下一个城市是第一个城市group[i].seq[CITY_NUM] group[i].seq[0];}/*//打印交配过后的种群for(int i 0; i GROUP_NUM; i) {cout i 、 ;for(int j 0; j CITY_NUM; j) {cout group[i].seq[j] ;}//cout 适应度为 group[i].fitness 生存概率为 group[i].Ps endl;cout endl;}*/
}//变异算法
//每个算子有一定概率变异概率基因多次对换。
//对每个个体若满足变异概率则随机生成两个不相等的范围在[0,城市数 - 1]之间的随机整数。将该个体在这两个随机整数对应的位置的城市编号对换
//进行上述n次对换n是一个[1,城市数]之间的随机整数
void mutate() {srand((unsigned)time(NULL));for(int i 0; i GROUP_NUM; i) {//生成0-1之间的随机数(4位小数)float random rand() % (10000) / (float)(10000);//cout random ;if(random Pm) {//cout i 号个体产生变异 endl;//随机生成基因对换次数int exchange_times rand() % CITY_NUM 1;while(exchange_times 0) {//随机生成两个不相等的范围在[0,城市数 - 1]之间的随机数int a rand() % CITY_NUM;int b rand() % CITY_NUM;swap(group[i].seq[a], group[i].seq[b]);exchange_times--;}}//最后一个城市的下一个城市是第一个城市group[i].seq[CITY_NUM] group[i].seq[0];}/*cout endl 打印变异过后的种群 endl;for(int i 0; i GROUP_NUM; i) {cout i 、 ;for(int j 0; j CITY_NUM; j) {cout group[i].seq[j] ;}//cout 适应度为 group[i].fitness 生存概率为 group[i].Ps endl;cout endl;}*/
}int main()
{int it 0; //迭代次数//随机生成初始城市坐标city_init();//随机生成初始种群group_init();cal_group();sort(group.begin(), group.end(),my_cmp);//show();cout endl;cout 初代“最优”路线为;for(int i 0; i CITY_NUM 1; i) {cout group[GROUP_NUM - 1].seq[i] ;} cout 适应度为 group[GROUP_NUM - 1].fitness endl;cout 该路线长度为 group[GROUP_NUM - 1].dis endl;cout 该路线对应的坐标点分别为 endl;for(int i 0; i CITY_NUM 1; i) {int t group[GROUP_NUM - 1].seq[i];cout ( city[t].x , city[t].y ) endl;}while(it ITERATION_NUM) {//计算适应度以及生存概率cal_group();//在种群中选择个体select();//种群进行交配mating();//种群中的个体产生变异mutate();it;} cout endl;sort(group.begin(), group.end(),my_cmp);//show();//cal_group();cout 经过 ITERATION_NUM 次迭代后 endl;cout “最优”路线为;for(int i 0; i CITY_NUM 1; i) {cout group[GROUP_NUM - 1].seq[i] ;} cout 适应度为 group[GROUP_NUM - 1].fitness endl;cout 该路线长度为 group[GROUP_NUM - 1].dis endl;cout 该路线对应的坐标点分别为 endl;for(int i 0; i CITY_NUM 1; i) {int t group[GROUP_NUM - 1].seq[i];cout ( city[t].x , city[t].y ) endl;}return 0;
}
3.选择适当可视化方法显示结果。
在程序中输出初代种群和迭代完成后种群的最优路线顺序以及城市坐标将坐标填入Excel表中生成平面坐标折线图对比初代种群和利用遗传算法得到的种群各自的最优路线。
下面选取几次对比较明显的测试 测试①
在Excel中画出两条路线作为对比 可以看出由于遗传算法本身存在一些缺点后面讨论不能得到最优解但对比初代种群的最优路线来看经过遗传算法得到的近似解明显比初代种群的要优很多。
测试②
在Excel中画出两条路线作为对比
测试③
结论 经过几次测试后发现由于遗传算法是一种启发式搜索算法只能尽可能得到最优解但往往只能得到近似解对比最终得到的解和初始路线可以看出经过遗传算法后是可以得到一个比较优化的解的而且在城市数量为15、种群规模为100迭代1000次的情况下每次运行都只需要0.2s左右的时间这体现了遗传算法的优势在城市规模不是很大的时候算法效率是非常高的。
4. 分析适应度函数对启发式搜索算法的影响。
遗传算法评价一个解的好坏不是取决于它的解的结构而是取决于该解的适应度值这正体现了遗传算法“优胜劣汰”的特点。遗传算法不需要适应度函数满足连续可微等条件唯一要求是针对输入可计算出能加以比较的非负结果。一般情况下适应度越大说明该个体适应性越强越不容易在自然选择中被淘汰因此本次TSP问题实验中将个体的适应度定义为城市序列中相邻两城的距离之和的倒数。
适应度函数也称评价函数是根据目标函数确定的用于区分群体中个体好坏的标准总是非负的任何情况下都希望它的值越大越好。在选择操作中会出现2个成为遗传算法欺骗的问题:
在遗传算法初期,通常会产生一些超常个体,按照比例选择法,这些超常个体会因竞争力突出,而控制选择过程,影响到算法的全局优化性能遗传算法后期,当算法趋于收敛时,由于种群中个体适应度差异较小,继续优化的潜能降低,可能获得某个局部最优解.因此,如果适应度函数选择不当就会产生以上的欺骗问题.因此适应度函数的选择对于遗传算法的意义重大。
5. *扩展选做题考虑不同数值N对最终结果和求解性能的影响。对于比较大的N是否设计更快速的近似方法代替原有算法。
查阅相关资料得知求解TSP问题中有两个比较优的算法遗传算法和蚁群算法从查阅资料的数据来看遗传算法在求解30城市一下的TSP问题时显示了很好的性能其最优解和平均接都好于蚁群算法但随着城市数量的增加基本遗传算法由于搜索范围扩大搜索好解的能力下降在既有的迭代次数内得出的结果和最优结果相差就越来越大虽然在没有发生早熟情况下足够多的运算次数可以搜索到好解但需要花费很长的时间而蚁群算法却表现出良好的性能在很少迭代次数内可以搜索到好解。
因此对于比较大的N用蚁群算法代替遗传算法能够提高效率。
四、总结心得
本次实验采用遗传算法求解TSP问题在一开始设置的参数种群规模、城市数、迭代次数、交叉率和变异率中常常不能得到较好的解通过测试发现在迭代几十次后往后迭代的种群几乎没有改变查阅资料得知这种现象称为遗传算法的“早熟现象”即在遗传算法实现过程中丧失了种群个体的多样性使个体中的基因趋于一致导致算法的搜索停止在局部无法实现在全局的搜索最终得到的是局部最优解。
出现早熟现象的原因主要有
群体规模当群体规模取值较小时虽然算法的收敛速度会很快但是生成的具有较高适应度的个体的数量会很少容易造成早熟现象的发生当群体规模取值较大时保证了参加遗传算法的群体的多样性能够产生具有较高适应度的个体增大了得到全局最优解的可能性但是增大了算法的计算量降低了收敛速度。选择操作在自然界中选择过程遵循着优胜劣汰的规律在遗传算法中这种规律是通过选择算子来实现的。选择操作主要是在本代种群中选择适应度较高的个体保留到下一代保证遗传算法得到最优解。选择操作通常使用轮盘赌选择方法增大了较高适应度值的个体被遗传的概率但是这样有可能淘汰掉本代种群中的最佳个体也有可能本代中的最佳个体通过交叉和变异操作之后以前良好的基因组合被破坏容易出现早熟现象。交叉概率和遗传概率在遗传算法中通过交叉和变异的操作保证了种群个体的多样性。传统的遗传算法中交叉概率和变异概率采用了固定值。如果交叉概率取值较大提高了交叉操作的速度同时也破坏了原来个体算法的寻优速度就会降低如果交叉概率取值较小会降低遗传个体的破坏性但是算法可能会过早地得到局部最优解。如果变异概率较小通过变异操作产生的新个体的数量也会变小随着遗传操作的进行适应度较高个体就会在群体中快速繁殖从而出现局部最优解出现早熟现象。
基于以上原因重新调整了这几个参数的设置测试的结果前面已经提到了这里不再赘述。总之在本次实验中由于所有操作都是随机发生的包括城市的坐标在选择、交叉、变异过程中有可能将原种群中优秀的个体淘汰了得不到最优解而且经过调整过后的参数也难免遇到早熟的现象但在多数情况下还是能得到较好的解的。
