www.pudn.com > GA_Knapsack.rar > GA_Knapsack.m, change:2011-11-28,size:7073b

```function [MaxCost MaxX] = GA_Knapsack(T)
%%=========================================================================
%% GA_Function.m
%% Genetic algorithm for optimizing a Multi-constrained Knapsack Problem
%% 2011.11.10

%% 输出符号：
%% MaxCost 每次迭代最优值向量
%% MaxX 最优染色体
%%
%% 输入符号：
%% T 迭代次数
%%
%% e.g. GA_Knapsack(100);
%%
%%=========================================================================
clf
global Orthogonal a b c;
a = [8 24 13 80 70 80 45 15 28 90 130 32 20 120 40;
8 44 13 100 100 90 75 25 28 120 130 32 40 160 40;
3 6 4 20 20 30 8 3 12 14 40 6 3 20 5;
5 9 6 40 30 40 16 5 18 24 60 16 11 30 25;
5 11 7 50 40 40 19 7 18 29 70 21 17 30 25;
5 11 7 55 40 40 21 9 18 29 70 21 17 35 25;
0 0 1 10 4 10 0 6 0 6 32 3 0 70 10;
3 4 5 20 14 20 6 12 10 18 42 9 12 100 20;
3 6 9 30 29 20 12 12 10 30 42 18 18 110 20;
3 8 9 35 29 20 16 15 10 30 42 20 18 120 20];
b = [550 700 130 240 280 310 110 205 260 275];
c = [100 220 90 400 300 400 205 120 160 580 400 140 100 1300 650];

if ~exist('RandSeed', 'var')
RandSeed = round(sum(100*clock));
end
rand('state', RandSeed); % initialize random number generator

OPTIONS.popsize = 100; % total population size
OPTIONS.Maxgen = T; % generation count limit
OPTIONS.m = 10;
OPTIONS.dim = 15; % number of genes in each population member
OPTIONS.pmutate = 0.1; % mutation probability
OPTIONS.pcross = 1;
Keep = 2;
Orthogonal = Orthogonal_table(3, 3);

for i = 1 : OPTIONS.popsize
Population(i).chrom = randint(1,OPTIONS.dim);
Population(i).cost = getCost(Population(i).chrom);
end
Population = Pop_Sort(Population);
MaxCost = Population(1).cost;
MaxX = Population(1).chrom;

tic;

% Begin the evolution loop
for GenIndex = 1 : OPTIONS.Maxgen

for k = Keep+1 : 2 : OPTIONS.popsize % begin selection/crossover loop
Cost = 0;
for i = 1 : OPTIONS.popsize
Cost = [Cost Population(i).cost];
end
% Select two parents to mate and create two children - roulette wheel selection
mate = [];
for selParents = 1 : 2
Random_Cost = rand * sum(Cost);
Select_Cost = Cost(1);
Select_index = 1;
while Select_Cost < Random_Cost
Select_index = Select_index + 1;
if Select_index >= OPTIONS.popsize
break;
end
Select_Cost = Select_Cost + Cost(Select_index);
end
mate = [mate Select_index];
end
Parent(1, :) = Population(mate(1)).chrom;
Parent(2, :) = Population(mate(2)).chrom;

% uniform crossover
for i = 1 : OPTIONS.dim
if OPTIONS.pcross > rand
child(k-Keep, i) = Parent(1, i);
child(k-Keep+1, i) = Parent(2, i);
else
child(k-Keep, i) = Parent(2, i);
child(k-Keep+1, i) = Parent(1, i);
end
end

end % end selection/crossover loop

% Replace the non-elite population members with the new children
for k = Keep+1 : 2 : OPTIONS.popsize
Population(k).chrom = child(k-Keep, :);
Population(k+1).chrom = child(k-Keep+1, :);
end

%     % Mutation
%     for individual = Keep + 1 : OPTIONS.popsize % Don't allow the elites to be mutated
%         for parnum = 1 : OPTIONS.dim
%             if OPTIONS.pmutate > rand
%                 Population(individual).chrom(parnum) = ~Population(individual).chrom(parnum);%（均匀变异）
%             end
%         end
%     end

%正交算子
for i = 1:3:OPTIONS.popsize-2
children = getOrAlter([Population(i).chrom;Population(i+1).chrom;Population(i+2).chrom]);
for j = 1:11
cost(j) = getCost(children(j,:));
end
[cost, indices] = sort(cost, 2, 'descend');
Population(i).chrom = children(indices(1),:);
Population(i+1).chrom = children(indices(2),:);
Population(i+2).chrom = children(indices(3),:);
end

% Make sure the population does not have duplicates.
Population = ClearDups(Population);

for i = 1 : OPTIONS.popsize
Population(i).cost = getCost(Population(i).chrom);
end
Population = Pop_Sort(Population);

MaxCost = [MaxCost Population(1).cost];
MaxX = Population(1).chrom;

disp(['The best of Generation # ', num2str(GenIndex), ' are ',...
num2str(MaxCost(end))]);

end

hold on;
plot(1:OPTIONS.Maxgen+1, MaxCost);
plot((1:OPTIONS.Maxgen),4015,'--r');
xlabel('迭代次数');
ylabel('适应值');
hold off;

toc;

return;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function cost = getCost(x)

global a b c;

[m n] = size(a);
for i = 1:m
y(i) = sum(a(i,:).*x);
end
% 罚函数
y = b - y;
cost = sum(c.*x) + 1000*(sum(y(find(y<0))));

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [Population, indices] = Pop_Sort(Population)
% Sort the population members from best to worst

% fisrt step
popsize = length(Population);
Cost = zeros(1, popsize);
indices = zeros(1, popsize);
for i = 1 : popsize
Cost(i) = Population(i).cost;
end
[Cost, indices] = sort(Cost, 2, 'descend');%sort

% second step
Chroms = zeros(popsize, length(Population(1).chrom));
for i = 1 : popsize
Chroms(i, :) = Population(indices(i)).chrom;
end

for i = 1 : popsize
Population(i).chrom = Chroms(i, :);
Population(i).cost = Cost(i);
end

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [Population] = ClearDups(Population)

size = length(Population);
dim = length(Population(1).chrom);

c = 5;
parnum = ceil(dim / c);
d = 5;
dnum = ceil(dim / d);

for i = 1 : size
for j = i+1 : size
if sum(Population(i).chrom ~= Population(j).chrom) < dnum
mutation_point = randperm(dim);
mutation_point = mutation_point(1:parnum);
Population(j).chrom(mutation_point)=~Population(j).chrom(mutation_point);
end

%         if isequal(Population(i).chrom, Population(j).chrom)
% %             Population(j).chrom = randint(1,dim);
%
%             mutation_point = randperm(dim);
%             mutation_point = mutation_point(1:parnum);
%             Population(j).chrom(mutation_point)= ~Population(j).chrom(mutation_point);
%         end
end
end

return;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function children = getOrAlter(parents)

global Orthogonal;
children = zeros(11,15);

for i = 1 : 9
children(i,:) = [parents(Orthogonal(i,1),1:5) ...
parents(Orthogonal(i,2),6:10) ...
parents(Orthogonal(i,3),11:15)];
end
children(10,:) = parents(2,:);
children(11,:) = parents(3,:);

return;

```