-
Notifications
You must be signed in to change notification settings - Fork 18
/
GA.m
198 lines (175 loc) · 5.31 KB
/
GA.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
% Genetic Algorithm (Simple Demo) Matlab/Octave Program
% Written by X S Yang (Cambridge University)
% Modified by Gary Li (University of Waterloo) 2014
% Usage: gasimple or gasimple('x*exp(-x)');
%This program is modified to satify the Job Scheduling problem
%For ECE457A, Unitersity of Waterloo, Summer, 2014
%costs, Best Solution
function [costs, schedule]=GA(jobs, numberOfMachines, maxGen)
global solnew sol pop popnew fitness fitold range userdefinedn chromesomesize jobList NumberOfMachines limitedRange;
range=[1 numberOfMachines]; % Range/Domain
% Initializing the parameters
rand('state' ,0'); % Reset the random generator
popsize=100; % Population size
MaxGen=100; % Max number of generations
count=0; % counter
nsite=2; % number of mutation sites
pc=0.95; % Crossover probability
pm=0.05; % Mutation probability
% Update the max generation number if max generation is given
if nargin>1,
MaxGen=maxGen;
jobList=jobs;
NumberOfMachines=numberOfMachines;
end
chromesomesize=length(dec2bin(numberOfMachines));
nsbit=length(jobs)*chromesomesize; % String length (bits)
userdefinedn=length(jobs); %user defined n
% Generating the initial population
popnew=init_gen(popsize,nsbit);
fitness=zeros(1,popsize); % fitness array
% Display the shape of the function
%x=range(1):0.1:range(2);
%plot(x,felement(x,userdefinedn));
fitold=fitness;
% Initialize solution <- initial population
solnew=zeros(popsize, userdefinedn);
limitedRange=max(abs(range));
costs=zeros(maxGen,1);
%TODO:populate row
for i=1:popsize,
solnew(i,:)=bintodec(popnew(i,:));
end
bestfun=zeros(MaxGen,1);
bestsol=zeros(MaxGen,length(jobs));
%Record as the history
fitold=fitness;
pop=popnew;
sol=solnew;
% Start the evolution loop
for i=1:MaxGen,
% Record as the history
for k=1:popsize,
if(fitness(k)>=fitold(k))
pop(k,:)=popnew(k,:);
sol(k,:)=solnew(k,:);
fitold(k)=fitness(k);
else
popnew(k,:)=pop(k,:);
solnew(k,:)=sol(k,:);
end
end
for j=1:popsize,
% Crossover pair
ii=floor(popsize*rand)+1;
jj=floor(popsize*rand)+1;
% Cross over
if pc>rand,
[popnew(ii,:),popnew(jj,:)]=crossover(pop(ii,:),pop(jj,:));
% Evaluate the new pairs
count=count+2;
evolve(ii);
evolve(jj);
end
% Mutation at n sites
if pm>rand,
kk=floor(popsize*rand)+1; count=count+1;
popnew(kk,:)=mutate(pop(kk,:),nsite);
evolve(kk);
end
end % end for j
% Record the current best
bestfun(i)=max(fitness);
bestsols=sol(bestfun(i)==fitness,:);
bestsol(i,:)=bestsols(1,:);
costs(i,:)=cost(bestsol(i,:), jobs, numberOfMachines);
end % end for i
% Display results
%set(gcf,'color','w');
%subplot (2,1,1);
%plot(bestsol);
%title('Plot of best solution of each generation');
%subplot(2,1,2);
%plot(bestfun);
%title('Fitness');
%output
schedule=bestsol(size(bestsol, 1),:);
%costOutput=cost(schedule, jobs, numberOfMachines);
end % end for gasimple
% All the sub functions
% generation of the initial population
function pop=init_gen(np,nsbit)
% String length=nsbit+l with pop(:,l) for the Sign
%pop=rand(np,nsbit)>0.5;
pop=randi([0 1],np,nsbit);
end % end for init_gen
% Evolving the new generation
function evolve(j)
global solnew popnew fitness fitold pop sol jobList NumberOfMachines;
solnew(j,:)=bintodec(popnew(j,:));
%TODO: cost(schedule, Jobs, numberOfMachine)
fitness(j)= 1 / (1 + cost( solnew(j,:),jobList,NumberOfMachines));
if fitness(j)>fitold(j),
pop(j,:)=popnew(j,:);
sol(j)=solnew(j);
% else
% popnew(j,:)= pop(j,:);
% solnew(j)=sol(j);
end
% Convert a binary string into a decimal number
end % end for evolve
function [decs]=bintodec(bins)
global chromesomesize userdefinedn limitedRange;
decs=zeros(1, userdefinedn);
index=1;
divisor=((2^chromesomesize)-1);
for deci=1:userdefinedn,
nindex=index+chromesomesize;
bin=bins(index:nindex-1);
num=bin(1:end); % get the binary
generated=0;
for i=1:length(bin),
generated=generated+num(i)*2^(length(bin)-i);
end
dec=round((generated/divisor)*(limitedRange-1))+1;
index=nindex;
decs(deci)=dec;
end
end % end for bintodec
% Crossover operator
function [c,d]=crossover(a,b)
nn=length(a)-1;
% generating a random crossover point
cpoint=floor(nn*rand)+1;
c=[a(1:cpoint) b(cpoint+1:end)];
d=[b(1:cpoint) a(cpoint+1:end)];
end % end for crossover
% Mutatation operator
function anew=mutate(a,nsite)
nn=length(a);
anew=a;
for i=1:nsite,
j=floor(rand*nn)+1;
anew(j)=mod(a(j)+1,2);
end
end % end for mutation operation
% function for question 3, assume every value in vector x is same
% value
% x is the input of each value in vector x, assume each vector is same
% n is the user defined variable, which implies the size of the input
function [result]=felement(x, n)
result=zeros(1,size(x,2));
for i=1:size(x,2),
absx = abs(x(i));
absxn(1:n) = absx;
iexp = linspace(2, n+1, n);
result(i) = sum(absxn .^ iexp);
end
end
function [result]=cost(schedule, jobs, numberOfMachines)
results=zeros(1,numberOfMachines);
for i=1:length(jobs)
results(schedule(i)) = results(schedule(i)) + jobs(i);
end
result=max(results);
end