الگوريتم ژنتيك (Genetic Algorithm) يك الگوريتم جست و جو براساس الگوي تكامل نسل ها در طبيعت است. ايده ي اين الگورتيم به شكل جدي پس از تحقيقات John Holland (Only the registered members can see the link) از دانشگاه مشيگان مطرح شد. در اين تاپيك به تدريج گام هاي استفاده از اين الگوريتم و كاربرد آن در بهينه سازي به خصوص بهينه سازي چند هدفه (Multi-Objective Optimization) مطرح خواهد شد.
نگاهي به يك مسئله ي بهينه سازي چند هدفه:
در بهينه سازي طراحي يك سيستم اگر مجموعه ي
X={x1,x2,..xm}
متغير هاي طراحي (Design Variable) باشند آن گاه طراح بايد اين متغير هاي طراحي را به گونه اي تغيير دهد كه مقادير مجموعه ي توابع هدف (Cost Function) اكسترمم شود:
F={f1,f2,...fn}
مثال:
در بهينه سازي طراحي يك تير طراح بايد مساحت سطح مقطع تير و طول تير را به گونه اي تغيير دهد كه اولا" تغيير شكل تير نسبت به بار وارد به تير كمينه باشد و همچنين تير كم ترين جرم را داشته باشد. در اين طراحي متغير هاي طراحي (D.V.) مساحت سطح مقطع و طول تير هستند و توابع هدف (C.F.) مقدار تغيير شكل تير و جرم آن هستند كه طراح سعي دارد مقدار آن ها را كمينه كند.
كاربرد الگوريتم ژنتيك در بهينه سازي:
الگوريتم ژنتيك يك روش جست و جوي مستقيم (Direct Search) در بهينه سازي محسوب مي شود زيرا مستقيما" با مقدار تابع هدف سر و كار دارد و برخلاف روش هاي Gradient Based از تابع هدف مشتق گيري رياضي نمي كند. در GA متغير هاي طراحي به شكل رشته هاي كروموزوم كد مي شوند و اين رشته ها فرآيند هاي تكامل طبيعي نظير توليد مثل (Crossover) و جهش (Mutation) را سپري مي كنند. در هر مرحله رشته هاي معيوب حذف شده (Termination) و رشته هاي برتر باقي مي مانند و ويژگي خود را به نسل بعد منتقل مي كنند. بدين ترتيب هر نسل جديد، برتر از نسل هاي قديمي خواهد بود. اين روند تكامل را بسته به كاربرد مسئله مي توان تا دست يابي به برترين نسل ادامه داد. در نهايت برترين رشته هاي كروموزومي به دست آمده Decode مي شوند تا بهينه ترين متغير هاي طراحي كه همان دغدغه ي طراح بودند، به دست آيند.
ravegoat
23-02-12, 21:42
تمامي متغير هاي طراحي بايد به صورت يك رشته تعريف شوند. روش GA ايجاب مي كند كه متغير ها مانند يك كروموزوم باشند تا بتوان فرآيند هايي نظير جهش را روي آن ها پياده سازي كرد. عمل تبديل متغير هاي طراحي به رشته را Coding مي گويند. فرضا" اگر متغير طراحي ما طول تير باشد مي توان براي تبديل آن به يك رشته آن مقدار طول را در مبناي عدد 2 بيان كرد. در اين صورت اگر طول تير 3 متر باشد، كروموزوم به شكل زير تعريف مي شود:
1|1|0|0|0|0|0|0
طول يك كروموزوم بستگي به گستردگي فضاي جست و جو ما دارد. در مثال بالا از 8 بيت استفاده شده است. فرض بر اين بوده است كه طول تير فقط در واحد هاي يك متري تغيير مي كند و در نتيجه اين مدل كدينگ مي تواند تيري با طول صحيحي بين 0 تا 255 متر را پوشش دهد. بديهي است كه براي گستره ي طول بزرگ تر بايد تعداد بيت ها را افزايش داد.
متغير هاي طراحي ما همواره مقادير عددي نيستند. مسئله ي فروشنده ي دوره گرد (Traveling Saleman Problem (Only the registered members can see the link)) در نظر بگيريم. در اين مسئله فروشنده بايد فرضا" از هشت جزيره ي A، B تا H به ترتيبي عبور كند كه حداقل فاصله ي ممكن براي سفر به تمام اين جزيره ها را پيموده باشد. در اين مسئله ترتيب پيمايش جزيره ها، متغير طراحي است و مسافت طي شده، تابع هدف خواهد بود كه مقدار آن بايد كمينه شود. براي كد كردن متغير طراحي مي توان اين ايده را به كار بست:
يك كروموزوم 8 بيتي تعريف مي كنيم كه بيت اول آن از سمت چپ، نام اولين جزيره اي است كه فروشنده به آن سفر مي كند. بيت دوم نام دومين جزيره اي خواهد بود كه فروشنده به آن مي رود و الي آخر. پس كروموزوم زير نشان مي دهد:
B|A|C|E|H|F|D|G
كه فروشنده سفر خود را از جزيره ي B آغاز كرده است. بعد به جزيره ي A رفته است و طبق همين روند، سفر او در جزيره ي G خاتمه يافته است.
همان طور كه ملاحظه مي كنيم روش Coding اختياري و به شكلي قراردادي است و ممكن است براي يك مسئله روش هاي مختلفي براي كدينگ وجود داشته باشد اما هر روش كدينگ حتما" (تاكيد مي شود حتما") بايد دو ويژگي زير را داشته باشد:
روش كد كردن بايد تمام فضاي جست و جو ي متغير هاي طراحي را پوشش دهد. از ديد رياضي كد كردن بايد از فضاي جست و جو به فضاي رشته ها پوشا باشد. اگر روشي حتي اگر يكي از حالت هاي فضاي جست و جو را نتواند پوشش دهد، آن روش كدينگ مناسب نخواهد بود. به عنوان مثال اگر روش كد كردن يكي از مقادير طول تير و يا يكي از حالت هاي سفر فروشنده در مثال هاي فوق را نتواند به شكل يك كروموزوم نشان دهد، نمي توان از آن روش كدينگ استفاده كرد.
روش كدينگ نبايد دو مقدار و يا دو حالت در فضاي جست و جو را با يك رشته ي يكسان نشان دهد. از ديد رياضي كد كردن بايد از فضاي جست و جو به فضاي رشته ها رفتار تابع را داشته باشد. در مثال فوق اگر روش كد كردن، دو طول مختلف تير را با رشته ي يكساني نمايش دهد، نمي توان از آن روش استفاده كرد.
لازم به ذكر است كه اگر كدينگ براي يك حالت در فضاي جست و جو، دو يا تعداد بيش تري رشته در نظر بگيرد، آن روش همچنان معتبر است. از ديد رياضي روش كدينگ الزما" نبايد يك تابع يك به يك باشد. در مثال فروشنده ي دوره گرد، مسافت طي شده در دو حالت زير با هم برابر اند:
B|A|C|E|H|F|D|G
G|D|F|H|E|C|A|B
به عبارتي يكي حالت مسير رفت و ديگري حالت مسير برگشت را نشان مي دهند.
توجه داشته باشيم كه هرچه روش Coding ساده تر باشد و براي تعريف آن از تعداد كم تري بيت استفاده شود، الگوريتم ژنتيك سريع تر عمل مي كند و عمل Decoding نيز ساده تر خواهد بود.
ravegoat
26-02-12, 00:07
جمعيت اوليه: مجموعه اي از كروموزوم ها هستند كه به شكل تصادفي توليد مي شوند و اولين نسل را براي سير تكامل به وجود مي آورند. در اين جمعيت تصادفي، هم احتمال حضور كروموزوم هاي برتر و هم احتمال حضور كروموزوم هاي معيوب وجود دارد.
فرض كنيم كه متغير هاي طراحي ما از جنس عدد هستند. اين اعداد را به مبناي 2 برده و با كروموزوم هايي به طول 8 بيت كد مي كنيم. در نتيجه يك كروموزوم تصادفي ،0 ها و يا 1 هايي را شامل مي شود كه به شكلي تصادفي در كنار هم قرار گرفته اند و يك رشته ي 8 بيتي را توليد مي كنند.
تعداد جمعيت اوليه:
تعداد جمعيت اوليه پارامتري تجربي است و به عوامل زير بستگي دارد:
طول كروموزوم ها: هر چه طول كروموزوم بيش تر باشد، تعداد جمعيت اوليه بايد افزايش يابد.
نوع داده در هر بيت كروموزوم : هر چه داده اي كه در يك بيت قرار مي گيرد تنوع بيش تري داشته باشد، تعداد جمعيت اوليه افزايش يابد. رشته اي كه هر بيت آن يكي از حروف الفبا را در خود جاي مي دهد نسبت به حالتي كه هر بيت مي تواند تنها مقدار صفر و يا يك را قبول مي كند، نياز به جمعيت اوليه ي بيش تري دارد.
سورس MATLAB براي توليد 150 رشته ي تصادفي به طول 8 بيت:
for i=1:150
for j=1:m
a=rand;
if a>=0.5
a=1;
else
a=0;
end
P(i,j)=a;
end
end
حال ماتريس P جمعيت اوليه ي ما را شامل شده است.
ravegoat
26-02-12, 23:20
رمز گشايي:
پس از توليد جمعيت اوليه بايد آن ها را رمز گشايي (Decode) كرد. رمز گشايي دقيقا" عكس عمل كد كردن است و هر كروموزوم را به عضوي از فضاي جست و جوي متغير هاي طراحي بر مي گرداند.
طبق مثال هاي گذشته، ما طول تير را براي آن كه تبديل به رشته كنيم، آن را به مبناي 2 برده و با يك 8 بيتي نمايش مي داديم. جمعيت اوليه ي ما در اين مثال، 8 بيتي هاي تصادفي خواهند بود كه اگر رمز گشايي شوند، هر كدام مقدار يك طول را بيان مي كنند. مثلا":
1|1|0|1|0|0|0|0
يكي از كرموزوم هاي جمعيت اوليه در مثال طراحي تير باشد. چون به هنگام كد كردن طول، عدد را از مبناي 10 به مبناي 2 برديم، براي رمز گشايي بايد رشته را از مبناي 2 به مبناي 10 برگردانيم:
تعيين مقدار تابع هدف و برازندگي:
پس از رمز گشايي تمام كروموزوم هاي جمعيت اوليه، مقادير تابع هدف را براي آن ها مي يابيم. اگر به خاطر داشته باشيد، تابع هدف همان تابعي است كه قرار است مقدار آن اكسترمم شود. پس:
Chromosome -Decode-> X -> F(X)
مثال:
فرض كنيد مي خواهيم مقدار مقاومت يك مدار الكتريكي (R) را به گونه اي تعيين كنيم كه بازده ي آن- F(R) -بيشينه شود. رابطه ي بين مقاومت الكتريكي مدار و بازده با استفاده از نظريه ي مدار ها تييعن شده است. جمعيت اوليه ي ما شامل 5 كروموزوم تصادفي است. اين كروموزوم ها را رمز گشايي مي كنيم و به مقادير زير مي رسيم:
Fitness
F(R)
R
0.1
10
25
0.17
17
50
0.13
13
100
0.2
20
200
0.4
40
500
برازندگي (Fintness) عبارت است از برتري يك گونه نسبت به ساير گونه ها در يك جمعيت كه به شكل زير به دست مي آيد:
كه n تعداد جمعيت اوليه است.
براي مثال فوق براي R=25 آن گاه F(R)=F(25)=10 ؛ در اين صورت برازندگي اين عضو برابر خواهد شد با:
(40 + 20 + 13 + 17 + 10)/10 = 0.1
به همين شكل برازندگي ساير عضو ها هم تعيين مي شود كه نتيجه ي آن در جدول بالا آورده شده است. برترين گونه R=500 است زيرا بازده ي مدار در اين حالت نسبت به ساير حالت ها بيشينه است و در نتيجه برازندگي اين گونه نيز نسبت به بقيه بيش تر خواهد بود.
ravegoat
29-02-12, 13:19
انتخاب (Selection)
عملگري هست كه نحوه ي شركت جمعيت ها براي تشكيل نسل هاي بعد را تعيين مي كند. از ديد بهينه سازي عملگر انتخاب بايد نسلي را تشكيل دهد كه جمعيت آن اطلاعات ارزشنمند تر و بهينه تري را نسبت به نسل قبلي داشته باشد. دو روش متداول در انتخاب عبارت اند از:
چرخ گردان (Roulette Wheel)
تورنومنت (Tournament)
روش چرخ گردان (Roulette Wheel)
در اين روش يك دايره يا ديسك داريم كه هر كروموزوم با توجه به برازندگي (Fitness) اي كه دارد بخشي از اين دايره (Circular Sector) را به خود اختصاص مي دهد به گونه اي كه مجموع سكتور هاي هر كروموزوم يك دايره ي كامل را تشكيل مي دهد. يك اشاره گر وجود دارد كه بر محيط اين دايره مماس است. زماني كه اين دايره را حول مركز آن بچرخانيم، دايره مي چرخد و پس از مدتي مي ايستد. در اين حالت اشاره گر به يكي از اين بخش هاي تعيين شده روي دايره اشاره مي كند. چون هر يك از بخش ها (سكتور) بيان گر يك كروموزوم است، اشاره گر در واقع يك كروموزوم را انتخاب مي كند.
شكل زير چرخ گردان مربوط به مثال پست قبل (تعيين مقدار مقاومت الكتريكي مدار) را نشان مي دهد:
6458
خط قرمز رنگ همان اشاره گر است كه كروموزومي با برازندگي 40% را انتخاب كرده است. واضح است كه هر چه يك كرموزوم برتر باشد، احتمال انتخاب آن بيش تر خواهد بود.
حال بياييم سورس MATLAB اين روش را نيز بنويسيم:
fitness=[0.1,0.17,0.27,0.13,0.2,0.4];
f1=cumsum(fintness);
a=rand;
for i=1:(size(f1,2)-1)
if a>=f1(i) && a<=f1(i+1)
selectedpop=pop(i,:);
break
end
end
در كد بالا آرايه ي fintness شامل مقادير برازندگي كروموزوم ها است. ماتريس pop جمعيت اوليه ي كروموزوم ها و ماتريس selectedpop جمعيت انتخاب شده است.
روش تورنومنت (Tournament)
اين روش به گونه هاي مختلف اجرا مي شود؛ از جمله شكل 2 Plus يا 4 Plus .
در روش 2 Plus از جمعيت اوليه، چهار كروموزوم به شكل تصادفي انتخاب مي شوند. كروموزوم هاي انتخابي اول و دوم از نظر مقدار برازندگي با هم مقايسه مي شوند و كروموزومي كه برتر باشد به مرحله ي بعد مي رود. همين مقايسه روي كروموزوم هاي انتخابي سوم و چهارم صورت مي گيرد تا كرموزوم برتر شناسايي شود. حال دو كروموزوم برتر داريم كه آن دو را نيز از نظر برازندگي با هم مقايسه مي كنيم. كروموزوم برتر كروموزومي خواهد بود كه به نسل بعد خواهد رفت:
1|1|0|0|1|1|0|1
1|1|0|0|1|1|0|1 برتر
1|1|1|0|1|1|0|1
1|1|0|0|1|1|0|1 برترين
0|0|0|0|1|1|1|1
1|1|0|0|0|1|0|0 برتر
1|1|0|0|0|1|0|0
روش 4 Plus هم به شكل مشابه اجرا مي شود با اين تفاوت كه در قدم اول 8 كروموزوم از جمعيت اوليه به شكل تصادفي انتخاب مي شوند.
ravegoat
29-02-12, 15:06
زادولد (Crossover)
عملي است كه از تركيب دو كروموزوم به عنوان والدين (Parents)؛ دو كروموزوم جديد به عنوان فرزند (Offspring) به وجود مي آورد. فرزندان بخشي از اطلاعات مادر و بخشي از اطلاعات پدر را به ارث مي برند. گونه هاي متداول توليد مثل به شكل زير است:
One-point Crossover
در اين روش كرموزوم مادر از يك نقطه ي مشخص به دو بخش تقسيم مي شود. كروموزوم پدر نيز از همان نقطه ي مشخص به دو بخش تقسيم مي شود. حال فرزند اول از اتصال بخش اول كروموزوم مادر و بخش دوم كروموزوم پدر متولد مي شود. فرزند دوم نيز از اتصال بخش اول كرموزوم پدر و بخش دوم كرموزوم مادر به وجود مي آيد. محل برش بايد به شكل تصادفي تعيين شود.
1|1|0|0|1|1|0|1 مادر
0|1|0|1|0|1|0|1 فرزند اول
1|1|0|0|1|1|0|0 فرزند دوم
0|1|0|1|0|1|0|0 پدر
Two-point Crossover
در اين روش كرموزوم مادر از دو نقطه ي مشخص به سه بخش تقسيم مي شود. كروموزوم پدر نيز از همان دو نقطه ي مشخص به سه بخش تقسيم مي شود. حال فرزند اول از اتصال بخش اول كروموزوم مادر ، بخش دوم كروموزوم پدر و بخش سوم كروموزوم مادر متولد مي شود. فرزند دوم نيز از اتصال بخش اول كروموزوم پدر ، بخش دوم كروموزوم مادر و بخش سوم كروموزوم پدر به وجود مي آيد. محل نقاط برش همچنان بايد به شكل تصادفي تعيين شود.
1|1|0|0|1|1|0|1 مادر
1|1|0|1|0|1|0|1 فرزند اول
0|1|0|0|1|1|0|0 فرزند دوم
0|1|0|1|0|1|0|0 پدر
Scattering Crossover
در اين روش ابتدا يك رشته ي باينري متشكل از صفر و يا يك هاي تصادفي به طول كرموزوم هاي جمعيت توليد مي شود. حال اگر بيت اول رشته ي باينري توليد شده يك باشد، بيت اول كروموزوم مادر و بيت اول كروموزوم پدر جاي خود را با يكديگر عوض مي كنند. ولي اگر بيت اول رشته ي باينري صفر باشد، اين جايگزيني صورت نمي گيرد. همين روند براي بيت هاي بعدي نيز تكرار مي شود. در نهايت مادر و پدر با جايگزيني بيت هاي خود طبق الگوي رشته ي باينري، دو فرزند به وجود مي آورند.
مادر:
A|C|D|A|B|C
پدر:
B|A|B|C|D|A
رشته ي باينري توليد شده به شكل تصادفي:
0|1|0|0|1|1
فرزند اول:
B|A|D|A|D|C
فرزند دوم:
A|C|B|C|B|A
جهش (Mutation)
عملي است كه يك بيت كروموزوم را به شكل تصادفي انتخاب كرده و مقدار آن را تغيير مي دهد:
0|1|1|0|0|0|1|1
<< جهش
0|1|1|0|1|0|1|1
ravegoat
29-02-12, 17:00
قبل از آن كه با نحوه ي تشكيل نسل بعد آشنا شويم، سوالي را مطرح مي كنيم:
" چه تعداد از جمعيت اوليه در توليد مثل شركت مي كنند؟ و چه تعداد از اين جمعيت اوليه دچار جهش مي شوند؟ "
براي پاسخ دادن به سوال فوق دو مفهوم را معرفي مي كنيم:
احتمال توليد مثل (Probability of Crossover يا Pc)
كميتي است كه احتمال شركت جمعيت اوليه در توليد مثل را تعيين مي كند. مقدار Pc بين 70% تا 95% است. اين به معني نيست كه فرضا" 70% از جمعيت اوليه در توليد مثل شركت مي كنند بلكه به اين معني است كه 70% احتمال دارد كه جمعيت در توليد مثل شركت كنند. به عبارتي ديگر ممكن است تمام جمعيت در زادولد شركت كنند و از طرفي هم ممكن است هيچ يك از كروموزوم ها در زادولد شركت نكنند.
سورس MATLAB اعمال احتمال توليد مثل در زاد ولد:
Pc=0.7;
for i=1:N/2
a=rand;
if a<=Pc
%Do Crossover
end
end
N تعداد جمعيت اوليه است.
احتمال جهش (Probability of Mutation يا Pm)
كميتي است كه احتمال جهش يافتن جمعيت اوليه را تعيين مي كند. مقدار Pm كوچك تر از 0.1 است. اين به اين معني است كه احتمال اين كه يك كروموزوم جهش يابد، كم تر از 10% است.
سورس MATLAB اعمال احتمال جهش در جهش يافتن:
Pm=0.1;
for i=1:N
a=rand;
if a<=Pm
%Do Mutation
end
end
N تعداد جمعيت اوليه است.
نحوه ي انتخاب نسل آينده:
فرض كنيم تعداد جمعيت اوليه برابر N، تعداد جمعيت حاصل از زادولد برابر P و تعداد جمعيت حاصل از جهش برابر Q باشد.
بقاي جمعيت:
اگر تعداد جمعيت اوليه N باشد، تعداد جمعيت نسل بعد نيز بايد N باشد.
براي تشكيل نسل جديد:
اگر P>N باشد: با روش چرخ گردان، N كروموزوم را از جميعت حاصل از زادولد انتخاب مي كنيم كه اين N كروموزوم نسل بعد را تشكيل مي دهند.
اگر P=N باشد: جميعت حاصل از زادولد همان جمعيت نسل بعد خواهد بود.
اگر P<N باشد: جميعت حاصل از زادولد را به نسل بعد انتقال مي دهيم و براي جبران كمبود جمعيت جهت حفظ بقاي آن اين گونه عمل مي كنيم:
اگر Q>N-P باشد: با روش چرخ گردان،N-P كروموزوم را از جميعت حاصل از جهش انتخاب مي كنيم كه اين كروموزوم ها به علاوه ي كروموزوم هاي زادولد، نسل بعد را تشكيل مي دهند.
اگر Q=N-P باشد: تمام جميعت حاصل از جهش به علاوه ي كروموزوم هاي زادولد، نسل بعد را تشكيل مي دهند.
اگر Q<N-P باشد: تمام جميعت حاصل از جهش به علاوه ي كروموزوم هاي زادولد به نسل بعد منتقل مي شوند اما به دليل كمبود جمعيت بقاي آن حفظ نمي شود. لذا با روش چرخ گردان، N-P-Q كروموزوم را از جمعيت اوليه انتخاب مي كنيم تا اين كمبود جمعيت جبران شود و نسل بعد شكل گيرد.
ravegoat
07-03-12, 22:29
در اين پست يك جمع بندي از GA براي بهينه سازي تك هدفه (تنها با يك تابع هدف) ارايه مي شود.
مراحل:
ما در ابتدا يك روش كد گذاري براي تبديل متغير هاي طراحي به كروموزوم تعريف كرديم.
به تعداد مشخص جمعيت اوليه به شكل تصادفي توليد كرديم.
ميزان برازندگي هر يك از كروموزوم ها را تعيين نموديم.
سپس عملگر هاي زاد ولد و جهش را پياده سازي كرديم و جمعيتي را براي نسل جديد انتخاب كرديم.
نسل جديد در قدم بعدي مي تواند يك جمعيت اوليه ي ديگر باشد. در نتيجه مراحل 2 تا 4 را دوباره مي توان روي آن اجرا كرد و نسل جديد تري را به وجود آورد. اين روند مي تواند باز هم ادامه يابد كه هر نسل جديد تر كروموزوم هاي برتري نسبت به نسل هاي قبلي دارد. اين كروموزوم هاي برتر اگر رمزگشايي شوند همان جواب بهينه ي مسئله خواهند بود.
ولي اين سوال پيش مي آيد:
توليد نسل هاي جديد تا چه موقع بايد ادامه پيدا كند؟
جواب:
تا زماني كه رشد توليد كروموزوم هاي برتر در نسل هاي بعدي متوقف شود. تعداد توليد نسل ها (تعداد تكرار) حداقل بايد 3 برابر تعداد جمعيت اوليه باشد.
بحث الگوريتم ژنتيك براي بهينه سازي تك هدفه در اين جا به پايان رسيد. فلوچارت اين الگوريتم نيز پيوست شده است. در ادامه سعي مي شود سورس كد هاي پياده سازي GA هم قرار داده شود.
به اميد خدا پس از اين مورد، بحث بهينه سازي چند هدفه با الگوريتم ژنتيك (MOGA) را آغاز خواهيم كرد.
:give_rose:
ravegoat
23-03-12, 22:51
با سلام!
قبل از هر چيز شروع سال 1391 خورشيدي رو همه ي دوستان عزيزم تبريك مي گم:party: و براي همگي سالي پر از شادي و موفقيت رو آرزو مي كنم.:love:
طبق قولي كه داده شده بود، سورس الگوريتم ژنتيك تك هدفه پيوست شد. براي افزايش سرعت برنامه و آشنايي با نظريه ي ماتريس ها در زبان هاي برنامه نويسي پايه، سورس به زبان VB.NET نوشته شده. اگر فرصت شد سورس متلب اون هم پيوست ميشه (كه البته خيلي ساده تر هم است). اين سورس كد براي يافتن مفدار بيشينه ي توابعي به شكل y=f(x) نوشته شده كه براساس اون ميشه حالت هاي پيچيده تر رو هم بررسي كرد.
نكته اي كه وجود داره، توليد نسل هاي ضعيف در برخي از اجر هاي اين برنامه هستش. سعي ميشه نسخه ي بهينه تر اين برنامه در آينده ي نزديك قرار داده بشه. لازم به ذكر است روند تصادفي تر در الگوي هاي تكاملي منجر به نتايج مطلوب تري ميشه. لذا براي اعمال يك روند تصادفي بهتر ميشد از الگوريتم توليد اعداد تصادفي RAN2 استفاده كرد تا شايد نتايج بهتري حاصل بشه.
آرمين:give_rose:
ravegoat
31-03-12, 20:18
تفاوت بنيادي GA در بهينه سازي تك هدفه (Single) و چند هدفه (Multi) در تعيين برازندگي است. در بهينه سازي تك هدفه تنها يك تابع هدف وجود دارد و برازندگي خيلي راحت تعريف مي شود. در حالي كه در بهينه سازي تك چند هدفه، حالتي ممكن است از ديد يك تابع هدف مطلوب باشد ولي از ديد تابع هدف ديگر مطلوب نباشد. لذا بايد روشي ابداع كرد تا بتواند برازندگي جمعيت را نسبت به چند تابع هدف تعيين نمايد. روش متداول جبهه بندي نقاط غير برتر (Non-dominant) است؛ بدين شكل كه نقاط طراحي در جبهه (Front) هاي مختلف دسته بندي مي شوند. سپس گونه هاي برتر در هر جبهه با الگوريتم هايي تعيين مي شوند كه معروف ترين آن ها به شرح زير اند:
معيار شلوغي (Crowding Distance) در NSGA II
Epsilon Elimination در MUGA
مفهوم Dominant Space در SPEA
هر يك از الگورتيم هاي فوق منحي نقاط Pareto را در اختيار ما قرار مي دهند كه يكي از هدف هاي مهم در بهينه سازي چند هدفه است زيرا طراح با بررسي Pareto Front مي تواند در مورد طراحي سيستم تصميم گيري كند. منحني Pareto مي تواند شامل نقطه ي مصالحه ي طراحي (Trade-Off) باشد كه توازني بين تمامي توابع هدف خواهد بود. شكل زير يك Pareto Front مربوط به دو تابع هدف را نشان مي دهد:
6745 (Only the registered members can see the link)
دوستاني كه تمايل دارند با جزئيات كامل اين مبحث آشنا شوند مي توانند اين كتاب (Only the registered members can see the link) را كاملا" رايگان دربافت نموده و مطالعه كنند.
ravegoat
24-06-12, 11:40
در مبحث آخر به سراغ بهينه سازي هاي چندهدفه رفتيم و 3 الگوريتم را نيز معرفي كرديم. يكي از متداول ترين الگورتيم ها در اين زمينه NSGA II است كه توسط Deb ارايه شده است. در اين الگوريتم جمعيت ها جبهه بندي مي شوند و سپس معيار شلوغي در هر جبهه محاسبه مي گردد. با استفاده از روش تورنومنت، كروموزوم ها انتخاب مي شوند و در توليد مثل و جهش شركت مي كنند. مجددا" جبهه بندي و معيار شلوغي براي جمعيت هاي توليد شده ي جديد تعريف مي شود و اين روند همچنان ادامه خواهد يافت.
سورس VB.NET اين الگوريتم پيوست شده و سورس متلب آن نيز در اين بخش انجمن (Only the registered members can see the link) موجود است.
ravegoat
02-04-13, 10:41
اجازه دهید که یک بار دیگر این مسئله و نحوه ی تعریف آن با GA را مرور کنیم:
در اين مسئله فروشنده بايد فرضا" از هشت جزيره ي A، B تا H به ترتيبي عبور كند كه حداقل فاصله ي ممكن براي سفر به تمام اين جزيره ها را پيموده باشد. در اين مسئله ترتيب پيمايش جزيره ها، متغير طراحي است و مسافت طي شده، تابع هدف خواهد بود كه مقدار آن بايد كمينه شود. براي كد كردن متغير طراحي مي توان اين ايده را به كار بست:
يك كروموزوم 8 بيتي تعريف مي كنيم كه بيت اول آن از سمت چپ، نام اولين جزيره اي است كه فروشنده به آن سفر مي كند. بيت دوم نام دومين جزيره اي خواهد بود كه فروشنده به آن مي رود و الي آخر. پس كروموزوم زير نشان مي دهد:
B|A|C|E|H|F|D|G
كه فروشنده سفر خود را از جزيره ي B آغاز كرده است. بعد به جزيره ي A رفته است و طبق همين روند، سفر او در جزيره ي G خاتمه يافته است.
در مسئله ی فروشنده ی دوره گرد (TSP) مجاز نیستیم از یک شهر بیش از یک بار عبور کنیم. در نتیجه اگر براساس تولید مثل های معرفی شده در این بخش (Only the registered members can see the link) بخواهیم این مسئله را حل کنیم در کروموزوم فرزند ممکن است یک شهر دو یا چند بار تکرار شود که برخلاف فرض مسئله خواهد بود. در چنین مواردی از تولید مثل هایی تحت عنوان Order Crossover استفاده می شود. روند کامل حل TSP با GA را می توانید از پیوست دریافت نمایید.
sina6866
08-06-13, 17:25
سلام.خستاه نباشيد..
با تشكر از سايت خوبتون ميخواستم خواهش كنم در مورد الگوريتم ژنتيك چند هدفي و NSGA و SPEA و نمودارهاي PDF و CDF بيشتر توضيح بدين..22 خرداد امتحان دارم...اكه ميتونين واسم ميل كنين..با تشكر
porebrahimisadeghGmail.com
ravegoat
09-06-13, 17:24
سلام.خستاه نباشيد..
با تشكر از سايت خوبتون ميخواستم خواهش كنم در مورد الگوريتم ژنتيك چند هدفي و NSGA و SPEA و نمودارهاي PDF و CDF بيشتر توضيح بدين..22 خرداد امتحان دارم...اكه ميتونين واسم ميل كنين..با تشكر
porebrahimisadegh@Gmail (Only the registered members can see the link).com
سلام!
عضویت تون رو در شهر سخت افزار تبریک می گم. :party:
الگوریتم ژنتیک چند هدفی (MOGA) بهینه سازی یه مسئله با الگوریتم ژنتیک هستش که در اون بیش از یک تابع هدف (Cost Function) وجود داشته باشه؛ فرضا" یه سازه رو چه جوری بهینه کنیم که هم جرم مناسبی داشته و هم مقاومت مناسبی. در این صورت بهینه کردن جرم و مقاومت به عنوان دو تابع هدف در تزاحم، یه بهینه سازی چند هدفی به حساب میاد. غالبا" در MOGA از مفهومی به نام Pareto جهت شناسایی نقاط بهینه ی طراحی استفاده میشه.
NSGA نسخه ای از الگوریتم ژنتیک برای بهینه سازی مسائلی با دو تابع هدف هستش. نسخه ی اولیه ی این الگوریتم سال 2002 توسط Deb ارایه شد و بعدا" نسخه ی بهبود یافته ی اون تحت عنوان NSGA-II توسط ایشون مطرح شد. در NSGA-II توسط مفهومی به نام معیار شلوغی، نقاط طراحی در جبهه ها (Pareto Front) انتخاب میشن به طوری که نفاط نزدیک به هم حذف و نقاط تنها به نسل بعد منتقل میشن. مفهوم معیار شلوغی تنها در فضای دو بعدی قابل تصوره. این الگوریتم پاسخ های بهتری رو نسبت به الگوریتم های هم رده ی خودش ارایه میده. برای اطلاعات بیش تر (Only the registered members can see the link)
SPEA نسخه ای از الگوریتم ژنتیک برای بهینه سازی مسائلی با بیش از یک تابع هدف هستش. در این الگوریتم با مفهومی به نام فضای غالب (قابل تعریف در هر فضای n بعدی) نقاط طراحی در جبهه ها انتخاب میشن. برای اطلاعات بیش تر (Only the registered members can see the link)
PDF یا تابع چگالی احتمالات نحوه ی توزیع احتمالاتی مقادیر یه متغیر رو بیان می کنه. فرضا" این تابع میگه اگه شما برید بازار و یه میله ی یک متری بخرید چقدر احتمال داره که این میله دقیقا" یک متر باشه و چقدر احتمال داره که این میله یک متر و دو سانتی متر باشه. برای اطلاعات بیش تر (Only the registered members can see the link)
CDF یا تابع توزیع تجمعی انتگرال زیر سطح PDF هستش. طبق مثال این تابع بهتون میگه میله ی یک متری که شما خریدید چقدر احتمال داره که طولش از یک متر و دو سانتی متر بیش تر باشه و یا چقدر احتمال داره که طول از یک متر کم تر باشه. برای اطلاعات بیش تر (Only the registered members can see the link)
لازم به ذکره که PDF و CDF دو تابع پرکاربرد در الگوریتم های بهینه سازی مقاوم (Robust) نظیر RDO یا RBDO محسوب میشن که نمونه ای از سورس متلب این نوع بهینه سازی ها از این پیوند (Only the registered members can see the link) قابل دریافته.
موفق باشید
آرمین
ravegoat
20-08-14, 18:57
در دو مقاله ی پیوست شده معیار هایی جهت تعیین تعداد نسل ها در الگوریتم ژنتیک و به عبارتی شرط توقف الگوریتم بهینه سازی ارایه شده است. این معیار ها با در نظر گرفتن پارامتر های مساله بهینه سازی تک هدفه و یا چند هدفه، کم ترین تعداد تکرار الگوریتم جهت همگرایی آن ارایه می کنند.
ariael
12-11-14, 17:51
سلام ببخشید این مثال میشه بگید چطور حل میشه
اعداد یک تا هفتاد به صورت هشت بیتی تعداد ژن سی تایی هفت عملگر جمع منها ضرب تقسیم رادیکال فاکتوریل رادیکال انجام بده
خیلی فوری
- - - Updated - - -
ایمیل من aria.abounouriGmail.com
ravegoat
12-11-14, 19:38
سلام ببخشید این مثال میشه بگید چطور حل میشه
اعداد یک تا هفتاد به صورت هشت بیتی تعداد ژن سی تایی هفت عملگر جمع منها ضرب تقسیم رادیکال فاکتوریل رادیکال انجام بده
خیلی فوری
با سلام!
به شهر سخت افزار خوش آمدید.
بنده فقط بخش اول سوالتون رو متوجه شدم:
اگر بخواهیم اعداد بین 1 تا 70 را با یک کروموزوم 8 بیتی بیان کنیم باید از یک نگاشت بهره ببریم. برای رمز کردن عدد آن را از یک کم کرده و سپس جز صحیح حاصل ضرب آن را در 3.71 می یابیم. در نهایت حاصل را از مبنای 10 به مبنای 2 می بریم.
برای رمز گشایی ما ابتدا کروموزوم 8 بیتی را از مبنای 2 به مبنای 10 می بریم و حاصل را بر 256 تقسیم می کنیم. عدد به دست آمده را در 69 ضرب کرده و در نهایت با یک جمع می کنیم.