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;