本文目录
使用轮盘赌法进行选择。
function childpop = selection(pop, fitvalue, leaving)% 选择% pop input 种群% fitvalue input 种群适应度值% leaving input 选出size(pop,1)-leaving个个体% childpop outupt 选择出的种群totalfit = sum(fitvalue);fitvalue = fitvalue ./ totalfit;fitvalue = cumsum(fitvalue);n = size(pop, 1) - leaving;rnum = sort(rand(n, 1));childpop = zeros(n, size(pop, 2));fitin = 1;newin = 1;while newin <= n if rnum(newin) < fitvalue(fitin)
childpop(newin,:) = pop(fitin,:);
newin = newin + 1;
else
fitin = fitin + 1;
endendend
MATLAB
随机选择两个个体,再随机选择一段基因进行交换,以完成交叉操作。交叉后可能会产生冲突(访问同一个城市两次),保持交换的基因段(之后简称为交换段)不变,取得冲突基因在交换段内的位置,将交换段外的冲突基因替换为另一染色体对应位置的基因。
比如下面两个个体之间交叉
A: 9 5 1 3 7 4 2 10 8 6 B: 10 5 4 6 3 8 7 2 1 9
得到
A: 9 5 1 6 3 8 7 10 8 6 B: 10 5 4 3 7 4 2 2 1 9
可见,二者交换的基因段为 6 3 8 7 和 3 7 4 2 ,保持此段不变,对于A,第一个冲突基因为8,取得8在交换段中的位置(6),将交换段外冲突基因替换为B中相应位置的基因,即4. 多次执行直到没有冲突,得到基因:
A: 9 5 1 6 3 8 7 10 4 2 B: 10 5 8 3 7 4 2 6 1 9
下面是代码实现:
function index = isconflict(v, left, right)% 判断向量内是否有冲突:是否有重复的城市% v input 城市序列% left input 忽略序列左索引% right input 忽略序列右索引% index output 0表示不冲突,其他表示冲突位置index = 0;for i = 1:length(v)
if i >= left && i <= right continue
end
n = size(find(v == v(i)), 2);
if n ~= 1
index = i;
break
endendend
MATLAB
function [rv1, rv2] = crossvector(v1, v2)% 交叉两个向量,并确保每个向量经过每个点一次% (v1, v2) input 需要交叉的两个向量% [rv1, rv2] ouptut 交叉完成后的两个向量% 随机生成交叉点len = length(v1);r1 = ceil(len * rand);r2 = ceil(len * rand);left = min([r1 r2]);right = max([r1 r2]);if left == right
rv1 = v1;
rv2 = v2;
returnend% fprintf('left=%d, right=%d\n', left, right);% 交叉tempv1 = [v1(1:left-1) v2(left:right) v1(right+1:len)];tempv2 = [v2(1:left-1) v1(left:right) v2(right+1:len)];% 解决冲突,确保一条路线覆盖每个点一次conflictindex = isconflict(tempv1, left, right);while conflictindex ~= 0
tempindex = find(tempv1(left:right) == tempv1(conflictindex));
tempv1(conflictindex) = tempv2(tempindex+left-1);
conflictindex = isconflict(tempv1, left, right);endconflictindex = isconflict(tempv2, left, right);while conflictindex ~= 0
tempindex = find(tempv2(left:right) == tempv2(conflictindex));
tempv2(conflictindex) = tempv1(tempindex+left-1);
conflictindex = isconflict(tempv2, left, right);endrv1 = tempv1;rv2 = tempv2;end
MATLAB
function childpop = crossover(pop, pc)% 交叉% pop input 种群% pc input 交叉概率% childpop output 交叉后的种群n = size(pop, 1);for i = 1:n if rand < pc
r1 = unidrnd(n);
r2 = unidrnd(n);% fprintf('r1=%d, r2=%d\n', r1, r2);
if (r1 == r2)
continue
end
[pop(r2,:), pop(r1,:)] = crossvector(pop(r1,:), pop(r2,:));
endendchildpop = pop;end
MATLAB
随机交换染色体中的两个基因的位置即可:
function childpop = mutation(pop, pm)% 变异% pop input 种群% pm input 变异概率% childpop output 变异后的种群[n, l] = size(pop);for i = 1:n if rand < pm
r1 = ceil(rand * l);
r2 = ceil(rand * l);
temp = pop(i, r1);
pop(i, r1) = pop(i, r2);
pop(i, r2) = temp;
endendchildpop = pop;end
MATLAB
function bestindex = bestindividual(fitvalue)% 得到最优个体索引% fitvalue input 适应度值% bestindex output 最优个体索引[~, bestindex] = max(fitvalue);end
MATLAB
function plot_pos(pos)% 绘制种群图(城市坐标图)% pos input 城市坐标% lx input 绘图横轴左边界% ux input 绘图横轴右边界% ly input 绘图纵轴下边界% uy input 绘图纵轴上边界plot(pos(1,:), pos(2,:), 'bo');title('种群图(城市坐标图)');end
MATLAB
function plot_route(pos, v)% 绘制路线图% pos input 城市坐标% v input 城市序列plot_pos(pos);hold on;for i = 1:(size(v,2)-1)
x1 = pos(1,v(i)); y1 = pos(2,v(i));
x2 = pos(1,v(i+1)); y2 = pos(2,v(i+1));
plot([x1, x2], [y1, y2], 'b');
hold on;endplot([pos(1,v(end)), pos(1,v(1))], [pos(2,v(end)), pos(2,v(1))], 'b');end
MATLAB