衢州市网站建设_网站建设公司_博客网站_seo优化

#MATLAB编写遗传算法，基于遗传算法求解TSP问题及函数最值最值问题。 #程序包含详细注释，本人在2020a版本均可运行。

% 种群初始化 population_size = 50; gene_length = 20; % 二进制编码长度 population = randi([0 1], population_size, gene_length);

这里用20位二进制表示一个数，相当于把[-5,5]区间细分成了2²⁰份。随机生成的50个二进制串构成初始种群，注意这里的二进制编码是实打实的0-1矩阵，看着像乱码其实藏着潜在解。

适应度计算更有意思，咱们把二进制转十进制后算目标函数：

function fitness = calc_fitness(pop) x = binary2real(pop); % 二进制转实数 fitness = 1./(x.^2 + 1e-5); % 防止除零 end

这里有个骚操作——取倒数让最小值问题转化为适应度最大化问题。加上1e-5避免除零，虽然数学上x=0时原函数最小，但实际运算中种群可能正好撞上这个点。

交叉操作来个两点交叉：

child = [parent1(1:cross_point1), parent2(cross_point1+1:cross_point2), parent1(cross_point2+1:end)];

这种交叉方式比单点交叉更灵活，特别是处理二进制编码时，能保留更多基因组合可能性。实测发现交叉概率设在0.6-0.8之间效果最佳，太高容易破坏优秀个体。

突然想试试更刺激的TSP问题。拿中国34个城市坐标开刀，先看距离矩阵生成：

dist_matrix = zeros(n,n); for i = 1:n for j = i+1:n dist_matrix(i,j) = norm(cities(i,:)-cities(j,:)); dist_matrix(j,i) = dist_matrix(i,j); end end

这个全连接矩阵会吃掉不少内存，不过34城市还在可接受范围。路径编码直接采用整数排列，比如[3,1,4,2]表示访问顺序，这种编码方式天然满足TSP的访问限制。

变异操作玩点花活——逆转变异：

mutate_point = sort(randperm(length(path),2)); mutated = [path(1:mutate_point(1)-1), fliplr(path(mutate_point(1):mutate_point(2))), path(mutate_point(2)+1:end)];

随机选两个点把中间路径反转，这种操作能在保持大部分路径结构的同时引入突变，实测比单纯交换两个城市位置更容易跳出局部最优。

跑完500代后的最优路径长度从初始的8万多公里降到3万以内，虽然离理论最优还有差距，但看着MATLAB生成的路径动画，城市连线从杂乱无章逐渐变成合理回路，这过程莫名治愈。关键代码其实就三大块：选择、交叉、变异，但调参真是玄学——种群规模太大收敛慢，太小容易早熟；突变率高了像无头苍蝇，低了又陷入局部最优。

最后扔个实用技巧：在迭代后期加入局部搜索能显著提升解的质量。比如对TSP当前最优解做2-opt优化：

for i = 1:length(path)-1 for j = i+2:length(path) new_path = path; new_path(i:j) = path(j:-1:i); if calc_distance(new_path) < current_best path = new_path; break; end end end

这种暴力邻域搜索虽然时间复杂度高，但在精英个体上偶尔用用效果拔群。遗传算法的魅力就在于这种全局探索与局部开发的平衡，就像人生既要大胆尝试又要专注深耕。