یک عیدی
نحوه ی اجرای برنامه
Main استفاده کنید و در اعلان آن نام تابع اصلی Matlab 7.1 برای اجرای برنامه از نسخه ی
را تایپ کنید.
برنامه شروع به کار می کند. در ابتدای برنامه چهارEnter و زدن Main بعد از نوشتن نام تابع
پارامتر از کاربردرخواست می شود که عبارتند از:
Pc,pm,pop_size,maxgen
لازم به ذکر است اگر هیچ مقداری به این پارامترها وارد نشود مقادیر پیش فرض در آنها ذخیره pc=0.90,pm=0.10,pop_size=10,maxgen=20می شود
سپس برنامه با مقادیر داده شده به کار خود ادامه می دهد. در ادامه صفحه ی رسمی ظاهر می شود که در آن به تعداد رکوردهای تولید شده در هر نسل یک منحنی به نمایش در می آید این منحنی نشان دهنده ی پیشرفت نسل ها در هر مرحله از برنامه می باشد . به خوبی و به وضوح پیشرفت برنامه از روی شکل قابل درک و فهم می باشد بعد از اتمام بر روی صفحه ی اصلی
(اعلان مطلب) سه خروجی دیده می شود. خروجی اول آخرین جمعیت (نسل) تولید شده که در طی عملیات مختلف بهینه شده اند به نمایش در می آید. خروجی دوم بهینه ترین رکورد را نمایش می دهد و خروجی سوم برنامه ی هفتگی رکورد بهینه را نمایش می دهد . در برنامه ی هفتگی زمان دروسی که در رکورد بهینه انتخاب شده اندبا مقدار 1 و بقیه ی اوقات با 0 پر شده اند به طوری که انتخاب ساعات 8و9و10 در ردیف سوم بیانگر وجود کلاس در روز دوشنبه از ساعت 8-11 می باشد .
جزئیات برنامه
توابع به کار رفته در برنامه:
: از این تابع برای فراخوانی برنامه ی اصلی که روابط دیگر توابع را با یکدیگر Main()تابع
مشخص می کند مورد استفاده قرار می گیرد.
استفاده می شود.crossover : ازاین تابع برای تولید نسل توسط عمل Crossover()تابع
: این تابع عمل جهش را بر روی رکوردهای تصادفی اعمال می کند.Mutation()تابع
را انجام می دهد.popsize : این تابع عمل گزینش رکوردهای بهینه به تعداد Select()تابع
: این تابع با اعمال شرایط پذیرش رکورد دارای شرایط را می پذیرد.Check()تابع
جمعیت اولیه تولید می شودPop_sizeدر ابتدای برنامه با مشخص کردن پارامتر ها به تعداد
به طوری که اگر رکورد تصادفی تولید شده شرایط را نقض نکند به جمعیت اضافه می شود شرایط برنامه به شرح زیر می باشد :
و عدم تداخل و عدم تکراری بودن.minunit >تعداد واحد>maxunit
فراخوانی می شود Crossover() تابع crossoverبعد از تولید جمعیت اولیه برای انجام عمل
به هر رکورد از جمعیت یک عدد تصادفی نسبت داده pcدر این فراخوانی ابتدا بر اساس پارامتر
می شود که درصد شرکت پذیری هر رکورد را مشخص می کند. در صورتی رکورد در عمل
کمتر باشد.pc شرکت خواهد کرد که مقدار عدد آن از crossover
سپس ترتیب رکوردها که به ترتیب صعودی بودند به هم می خوردزیرا در غیر این صورت می می شود و این باعث جلوگیری از تولید نسل crossoverهمواره رکورد های بهتر با هم دیگر
پراکنده می شود که در مراحل بعدی به یک جواب همگرا می شوند. در ادامه رکورد ها دو به دو ارسال میcheck را انجام می دهند و بعد از تولید رکورد فرزند به تابع crossoverبا هم عمل
شود تا عدم نقض شروط تایید شود. سپس رکورد فرزند به انتهای جمعیت اضافه می شود.
فراخوانی می شود. در این تابع یک عدد تصادفی بهMutation در ادامه ی اجرای برنامه تابع
هر رکورد نسبت داده می شود که این عدد درصد شرکت پذیری رکورد در عمل جهش را کمتر باشد رکورد در عمل جهش شرکت خواهد کرد.pmمشخص می کند. اگراین عدد از مقدار پارامتر
بعد از مشخص شدن رکورد ها محل جهش به صورت تصادفی مشخص می شودسپس جهش فرستاده می شود. اگر تلبع چک رکورد جهش checkاعمال می شودو برای چک کردن به تابع
یافته را تایید کرد رکورد به انتهای جمعیت اضافه می شود.در غیر این صورت رکورد از بین می رود.
برای هر رکورد یک معیاری بهselectدر ادامه نوبت به عمل انتخاب می رسد. با فراخوانی تابع
در نظر گرفته می شود روال کار طوری است که هر رکوردی که مقدار minimizationنام
آن از همه کمتر باشد انتخاب می شود . تعداد رکورد های انتخابی باید دقیقا به minimization
به اندازه ی رکوردهای جمعیت اولیه باشد و بقیه ی رکوردهای باقیمانده حذف می شود.
با گزینش رکورد های جدید یک نسل به وجود می آید و نسل جدید خود را برای تکرار عملیات قبلی آماده می کند.
گزارش گیری از برنامه:
تاثیر پارامتر ها در روند برنامه :
در روند برنامه :pcالف) تاثیر پارامتر
را مشخص می کند بنابراینCrossover در صد شرکت پذیری رکوردها درعمل pcپارامتر
شرکت می کنند لذا در ابتدایcrossover بالا رود رکورد های بیشتری در عمل pcهر چه درصد
اجرا الگوریتم به سمت جواب های بهینه با سرعت بیشتری حرکت می کند علت این است که در ابتدا به خاطر فراوانی انواع داده و انتخاب رکوردها به صورت پراکنده جواب های گوناگونی تولید می شود . این روند تا چندین مرحله به این صورت ادامه پیدامی کند بعد کم کم جواب ها به کم رنگتر میشود زیرا بعد از عمل pcصورت تکراری ظاهر می شود که در این موقع تاثیر
شرکت کرده اند.crossover فرزندان تولید شده همان والدینی هستند که در عمل crossover
بیشتر ظاهر می شود. crossover در مراحل ابتدایی pcدر حالت کلی تاثیر
بالا رود سرعت همگرایی جواب ها بالا می رود ولی بعد از چندین pcاز طرفی اگر درصد
مرحله به بعد جواب ها تکرار می شوند.
رکوردهای کمتری شرکت crossover پایین در نظرگرفته شود در عمل pcدر مقابل اگر درصد
می کنند که این امر باعث می شود تا رکوردهای جدید کمتری تولید شوند به عبارت دیگر پراکندگی داده ای کمتری خواهیم داشت.لذا پیش فرض انتخاب شده برابر 0.90 می باشد.
pcمعایب بالا بودن
pc بالا رود به علت وابسته بودن تعداد عملیات انجام گرفته به درصد pcهر چه درصد
زمان اجرایی بالا می رود.
در روند برنامه :pmب) تاثیر درصد
درصد شرکت پذیری رکوردها در عمل جهش را مشخص می کند. عمل جهشpmدر حالت کلی
در مواقعی که رکوردها به یک جواب خاص همگرا می شوند به کمک برنامه می آید خواه این جواب بهینه باشد یا بهینه نباشد.
0.10 می باشدکه تقریبا از ده رکورد یک رکورد در عمل جهش pmدر این برنامه پیش فرض
شرکت می کند. اگر این عمل باعث نا معتبر شدن رکورد گردد به جمعیت رکوردها اضافه نمی شود ولی اگر معتبر بود به جمعیت اضافه می شود اگر در این میان رکورد جهش یافته به سمت جواب بهینه تر باشد بقیه ی رکوردها را در نسل های بعدی به سمت جواب های بهینه سوق می دهد.
ولی اگر جواب بهتری نداشته باشد در مراحل بعدی خود به خود ازبین می رود.
علت بهینه شدن بقیه ی جواب ها در نسل های بعدی (در صورت بهینه بودن رکورد جهش یافته) نسل بعدی است که در نسل های بعدی باعثcrossoverشرکت کردن رکورد جهش یافته در عمل
سوق دادن بقیه ی رکوردها به سمت جواب بهینه می شود.
درصد شرکت پذیری رکوردها در عمل جهش را مشخص می کند لذا هر چهpmبه خاطر اینکه
بالا رود رکوردهای جهش یافته ی بیشتری خواهیم داشت بنابراین احتمال جهش(پرش)pmمقدار
pmدر حالتی که رکوردها به یک جواب همگرا می شوند زیاد می شود. ولی با بالا رفتن درصد
زمان اجرا بالا می رود از طرفی عمل جهش بیشتر در مراحل پایانی به کمک برنامه می آید زیرا بستگی دارد.pc صفرهم باشد باز هم روند برنامه به pmدر مراحل ابتدایی حتی اگر مقدار
ولی در مراحل پایانی به علت همگرا شدن جواب ها یک جهش مثبت لازم است تا در نسل های pmدر ابتدای برنامه و بعد از عمل جهش وpcبعدی جواب های بهتری ظاهر شوند. در نهایت
در خود عمل جهش تاثیر دارد.
در روند برنامه :Pop_sizeج) تاثیر
Pop_sizeمقدار این مولف بیانگر تعداد جمعیت اولیه می باشد. در ابتدای اجرای برنامه به مقدار
جمعیت اولیه به صورت تصادفی ایجاد می شود.به علت تصادفی بودن مقادیرممکن است جمعیت pop_sizeتعداد جمعیت بر اساس pm,pcپراکنده باشد یا نباشد. در مراحل بعدی بسته به مقدار
کاهش Pop_size جمعیت افزایش یافته به تعداد selectافزایش پیدا میکند.سپس در مرحله ی
رابطه ی مستقیم داردPop_size می یابد لذا مرتبه ی اجرایی و پیچیدگی زمانی برنامه با مقدار
افزایش پیدا کند زمان اجرا بالا می رود.Pop_sizeیعنی هر چه مقدار
در روند برنامه :Max_genد) تاثیر
را مشخص می کند. تعداد دفعات Crossover,mutation,selectاین متغیر تعداد تکرار عملیات
تکرار رابطه ی خاصی با پیدا شدن جواب ها ندارد زیرا ممکن است پراکندگی دادها طوری باشد ام به جواب بهینه برسیمmام به جواب بهینه برسیم و در دیگری در نسل nکه در اجرا در نسل
ولی به علت تکرار شدن و زمان بر بودن عملیات زیاد شدن تعداد تکرار زمان پاسخ دهی را افزایش می دهد.
در مواقع یپیش می آید که جوابها به سمت یک جواب همگرا می شوند که در این حالت تکرار عملیات بیهوده بوده و برای سیستم سربار می باشد در این حالت شرط خروج را می توان هم از روی تعداد تکرار نسل ها و هم از روی همگرایی جوابها مشخص کرد.
آزمون و تجربه نشان می دهد زمانی که جوابها همگرا می شوند یک عمل جهش ممکن است که برنامه را از این حالت در بیاورد ولی دقیقا مشخص نیست که در کدام مرحله از تکرار عمل جهش کارساز خواهد بود بنابراین باز هم تخمین تعداد تکرار نسلها سخت و حتی غیر ممکن است
سورس برنامه الگوریتم ژنتیک
clear
global pc pm pop_size max_gen minunit maxunit input_data
pc=0.90;
pm=0.1;
pop_size=10;
max_gen=20;
pc_temp=input('enter Pc (Blank for default)');
pm_temp=input('enter (Blank for default)');
pop_size_temp=input('enter (Blank for default)');
max_gen_temp=input('enter (Blank for default)');
if isempty(pc_temp)
pc;
else
pc=pc_temp;
end
if isempty(pm_temp)
pm;
else
pm=pm_temp;
end
if isempty(pop_size_temp)
pop_size;
else
pop_size=pop_size_temp;
end
if isempty(max_gen_temp)
max_gen;
else
max_gen=max_gen_temp;
end
file2mat=dlmread ('INFILE.txt');
minunit=file2mat(1,1);
maxunit=file2mat(2,1);
input_data=file2mat(3:end,:);
[rec_length,col]=size(input_data);
pop_record(1,:)=(rand(1,rec_length)).*0;
i=0;
while i
c=check(new_record,pop_record );
if c==1
pop_length=size(pop_record);
for count=1:pop_length(1)
if new_record==pop_record(count,:)
new_record;
pop_record;
else
i=i+1;
pop_record(i,:)=new_record;
end
end
end
end
for gen_count=1:max_gen
co=int2str(gen_count);
xlabel(co)
pause(0.5)
pop_record=crossover(pop_record,rec_length);
pop_record=mutation(pop_record,rec_length);
pop_record=select(pop_record,rec_length);
end
%************ Display Minimal_Record that contain the lessons **************
day=['Sat' 'Sun' 'Mon' 'Sun' 'Tue' 'Wed'];
Minimal_population=pop_record
The_First_Minimal_Record=pop_record(1,:)
week=fix(rand(8,12));
week(1,:)=8:19;
week;
ones=find(The_First_Minimal_Record==1);
size_ones=size(ones);
for m=1:size_ones(2)
time=input_data(ones(m),[4 5]);
a=time(1)-7;
b=time(2)-8;
c=input_data(ones(m),3);
week(input_data(ones(m),3)+2,[a:b])=1;
end
Barnameye_haftegi=week
%end
clear
????????????????????????????????
chek
function c=check(new_record,pop_record)
global minunit maxunit input_data
ones=find(new_record==1);
unitnum=sum(input_data(ones,6));
if unitnum
c=0;
return
else
size_ones=size(ones);
for i=1:size_ones(2)
count=0;
contact=0;
for x=1:size_ones(2)
if (input_data(ones(i),3) == input_data(ones(x),3)) & (input_data(ones(i),4) == input_data(ones(x),4)) & (input_data(ones(i),5) == input_data(ones(x),5))
count=count+1;
if count>1
c=0;
return
end
end
if (input_data(ones(i),3) == input_data(ones(x),3)) & (((input_data(ones(i),4) > input_data(ones(x),4)) & (input_data(ones(i),4) < input_data(ones(x),5))) | ((input_data(ones(i),5) > input_data(ones(x),4)) & (input_data(ones(i),5) < input_data(ones(x),5))) );
contact=contact+1;
if contact>1
c=0;
return
end
end
end
end
repeat=size(input_data(ones,2));
for i=1:repeat(1)
contact=0;
for x=1:repeat(1)
if (input_data(ones(i),3) == input_data(ones(x),3)) & (((input_data(ones(i),4) > input_data(ones(x),4)) & (input_data(ones(i),4) < input_data(ones(x),5))) | ((input_data(ones(i),5) > input_data(ones(x),4)) & (input_data(ones(i),5) < input_data(ones(x),5))) );
contact=contact+1;
if contact>1
c=0;
return
end
end
end
rep_les=size(find(input_data(ones,2)==input_data(ones(i),2)));
rep_les(1);
if rep_les(1)>1
c=0;
return
else
rep_les=[0 0];
end
end
end
c=1;
end
%end
???????????????????????????????
crossover
function [pop_record]=crossover(pop_record,rec_length)
global pc minunit maxunit input_data pop_size
pc_percent=find(rand(1,pop_size)
j=1;
for sort_count=pop_size:-1:1
rec_num=round((sort_count-1)*rand+1);
pop_temp2(sort_count,:)=pop_record(rec_num,:);
pop_record(rec_num,:)=[];
sort_count;
end
pop_record=pop_temp2;
for i=1:fix(c/2)
cut_pos=round((rec_length-2)*rand)+1;
cross_record_a=pop_record(pc_percent(j),:);
cross_record_b=pop_record(pc_percent(j+1),:);
temp=cross_record_a(1,cut_pos+1:rec_length);
cross_record_a(1,cut_pos+1:rec_length)=cross_record_b(1,cut_pos+1:rec_length);
cross_record_b(1,cut_pos+1:rec_length)=temp(1,:);
j=j+2;
c=check(cross_record_a,pop_record);
if c==1
pop_record(end+1,:)=cross_record_a;
end
c=check(cross_record_b,pop_record);
if c==1
pop_record(end+1,:)=cross_record_b;
end
end
return
end
%end
???????????????????????????????
mutation
function [pop_record]=mutation(pop_record,rec_length)
global pm minunit maxunit input_data pop_size
c=0;
pop_num=size(pop_record);
pm_percent=find(rand(1,pop_num(1))
for i=1:c
mut_pos=round((rec_length-2)*rand)+1;
mut_record=pop_record(pm_percent(i),:);
mut_record(1,mut_pos)=1-mut_record(1,mut_pos);
c=check(mut_record,pop_record);
if c==1
pop_record(end+1,:)=mut_record;
return
end
end
if c==0
for mut_count=1:20
mut_pos=round((rec_length-2)*rand)+1;
random_rec=round((pop_num(1)-1)*rand+1);
mut_record=pop_record(random_rec,:);
mut_record(1,mut_pos)=1-mut_record(1,mut_pos);
c=check(mut_record,pop_record);
if c==1
pop_record(end+1,:)=mut_record;
return
end
end
end
return
end
????????????????????????????????/
select
function [pop_record]=select(pop_record,rec_length)
global minunit maxunit input_data pop_size
pop_num=size(pop_record);
simple_days=[0 0 0 0 0 0];
for i=1:pop_num(1)
week=fix(rand(7,12));
week(1,:)=8:19;
ones=find(pop_record(i,:)==1);
days=(input_data(ones,3))';
k=0;
l=0;
for j=0:6
c=size(find(days==j));
if c(2)>0
k=k+1;
end
end
size_ones=size(ones);
for m=1:size_ones(2)
time=input_data(ones(m),[4 5]);
a=time(1)-7;
b=time(2)-8;
c=input_data(ones(m),3);
week(input_data(ones(m),3)+2,[a:b])=1;
end
week;
gap_total=0;
for z=2:7
ones_gap=find(week(z,:)==1);
if ones_gap ~= 0
gap_start_end=[ones_gap(1) ones_gap(end)];
gap_rec=find(week(z,gap_start_end(1):gap_start_end(2))==0 );
gap_size=size(gap_rec);
gap=gap_size(2);
gap_total=gap_total+gap;
else
gap_start_end=0;
end
end
gap_total;
minimization(i)= 3*k+gap_total;
clear simple_days
end
minimization;
c1=size(minimization);
x1=1:c1(2);
plot(x1,minimization,'*r')
axis([0 2*pop_size+5 0 50])
for j=1:pop_size
Min=min(minimization);
result=find(minimization==Min);
min_num=result(1,1);
minimization(min_num)=inf;
pop_temp(j,:)=pop_record(min_num,:);
end
clear pop_record
pop_record=pop_temp;
%end