最优化——关于遗传算法的补充(应试篇)

应用

二元函数的最大值求解

求 解 m a x f ( x , y ) = 3 ( 1 − x ) 2 e − x 2 − ( y + 1 ) 2 − 10 ( x 5 − x 3 − y 5 ) e − x 2 − y 2 − 1 3 e − ( x + 1 ) 2 − y 2 其 中 x ∈ [ − 3 , 3 ] , y ∈ [ − 3 , 3 ] 求解 max \quad f(x,y) = 3(1-x)^2 e^{-x^2-(y+1)^2} -10 (\frac{x}{5}-x^3-y^5) e^{-x^2-y^2} -\frac{1}{3}^{e^{-(x+1)^2-y^2}} \\ 其中 x \in [-3,3], y\in [-3,3] maxf(x,y)=3(1x)2ex2(y+1)210(5xx3y5)ex2y231e(x+1)2y2x[3,3],y[3,3]

(早知道直接附图片了,这公式套娃敲得累死。。。)

题目和算法思路全部来自于大佬博客:https://blog.csdn.net/ha_ha_ha233/java/article/details/91364937

TSP问题

(直接附上实验报告的说明,觉得自己写的还是比较清楚的。)

完整算法思路

该问题使用欧式距离来计算两个城市之间的距离,首先从cities.csv文件中读取坐标数据,然后利用这些数据来生成对称的邻接矩阵。通过该邻接矩阵我们可以在计算个体适应度函数时直接读取邻接矩阵的值。为了解决该tsp问题,我们首先对每一种可以选择路径进行编码,一共10个城市,染色体分为10段对应于每个城市的编号。初始的种群数量设置为100个。适应度函数选择为一个个体每两个相邻基因(城市)之间的距离之和的负数,这样可以使得距离之和越小的个体适应度函数值越大,越有可能在之后的遗传过程中被保留下来。

遗传过程采用轮盘赌选择法,每个个体被选择的概率和其适应度值成比例,适应度越大,被选中的概率也就越大。首先计算出每个个体被选中的概率,按照选择概率由小到大排序后再计算每个部分的累计概率。最后随机生成一个位于0~1之间的概率p,若累计概率中第i个个体大于数组中的元素,则该个体被选中,否则比较下一个个体,直到选择出一个个体为止。

选择出个体之后进行交叉和变异操作作为一次遗传过程。交叉采用两点交叉,即随机生成两个0~10的不相等整数作为交叉的位置。将需要交叉的部分进行切片记录。然后为了保证每个个体当中不包含重复的基因(即不经过相同的城市),需要进行冲突检测。冲突检测有四个部分,即两个父代的头部和尾部。如果发现这四个部分中有基因和交叉过来的部分重合,则将其映射为交叉之前的基因直到没有冲突情况出现。变异操作即选择两点进行位置交换。该问题交叉率被设置为0.7,变异率设置为0.3。再发生遗传操作之前随机生成相应的概率p,只有p小于相应的概率才会发生交叉和变异操作。此外,需要注意的是,已经发生交叉操作的个体会被移除待遗传的种群,不参加后面的交叉。

再设置好一次完整的遗传过程之后,该问题的遗传次数设置为50次,遗传过程结束之后输出此时种群中适应度最好的个体就是我们所需要的最优路径。

你可能感兴趣的