دانشگاه تهران

 

دانشکده فنی و مهندسی

گروه مهندسی کامپیوتر

 

پایان نامه کارشناسی 

گرایش نرم افزار

 

عنوان:

حل مسئله زمانبندی کارها با بهره گیری از

رویکرد تکاملی

 

استاد راهنما:

جناب آقای دکتر بیگلر بیگی

 

نگارش:

 مهندس محمد نظری زاده

 

 

زمان:

تابستان ١٣٩١

 

فهرست مطالب پایان نامه

 

الگوريتم هاي ژنتيک…. 8

Genetic Algorithms 7

1-1 مقدمه. 8

2-1 الگوريتم ژنتيک چيست؟. 10

3-1 ايده اصلي.. 14

4-1 الگوريتم.. 15

5-1   سود و کد : 16

6-1 روش هاي نمايش…. 18

8-1 روش هاي انتخاب… 19

9-1 روش هاي تغيير. 20

10-1 تقاط قوت الگوريتم هاي ژنتيک…. 21

11-1 محدوديتهاي  GAها 23

12-1 چند نمونه از کاربرد هاي الگوريتم هاي ژنتيک…. 23

13-1 نگاهی ریزتر بر پردازش تکاملی و الگوريتمهای ژنتيک…. 25

14-1 زمانبندی انجام کارها با کمترین زمان تاخیر با استفاده الگوریتم ژنتیک : 40

الگوريتم کلونی مورچگان.. 41

Ant Colony Algorithm… 41

1-2 مقدمه : 42

2-2 بهينه سازي مسائل بروش کلوني مورچه(ACO) : 43

2-2-2 مورچه ها چگونه مي توانند کوتاهترين مسير را پيدا کنند؟. 43

3-2 مزيتهاي ACO : 45

5-2 زمانبندی انجام کارها با کمترین زمان تاخیر با استفاده از الگوریتم کلونی مورچگان : 46

مسئله زمانبدی کارها با احتساب کمترین زمان تاخیر. 47

1-3 تعریف مسئله : 48

2-3 ارائه یک الگوریتم ژنتیک برای مسئله زمان بندی کار ها : 49

3-3 ارائه یک الگوریتم Ant Colony برای مسئله زمانبندی کارها : 50

کد های مر بوط به پیاده سازی پروژه با ژنتیک در زبا ن برنامه نویسی Visual C#.Net. 52

پیوست 2: 65

کد های مربوط به پیاده سازی پروژه با استفاده از الگوریتم کلونی مورچگان زبا نبرنامه نویسی Visual C#.Net  65

منابع : 7

 

چکیده :

در این پایان نامه با توجه به آموخته های دوره ی کارشناسی و اطلاعاتی که در زمینه علم ژنتیک کسب شده است سعی بر آن است که مسئله زمانبندی کارها با کمترین زمان تاخیر را که یک مسئله NP-Hard است را با دو الگوریتم غیر قطعی هوش مصنوعی حل شود که دیگر مشکل زمان اجرا برای حل این مسئله وجود نداشته باشد دو الگوریتم مورد استفاده، ابتدا در بخش اول مسئله با الگوریتم ژنتیک حل می شود ، در ادامه همان مسئله را با الگوریتم کلونی مورچگان مورد بررسی قرار می دهیم، اگر شرح کلی بر مسئله داده شود، در ورودی مسئله ابتدا تعداد کارها داده می شود که به ازای هر کار سه ورودی مهلت، ارزش و زمان اجرا وجود خواهد داشت هدف از حل مسئله بدست آوردن ترتیب خاصی از اجرای تمامی این کار ها بر روی سیستم عامل است به طوری که کمترین زمان تاخیر کل را  داشته باشد.

 

 

با سپاس :

از تمامی کسانی که در این مرحله از زندگی اینجانب زحمات فراوانی کشیده اند خصوصاٌ پدر و مادرم که مرا در تمامی مراحل زندگی یاری نمودند و با سپاس فراوان از استاد گرامی آقای مهندس بیگلر بیگی و همچنین از همه عزیزانی که در مراحل تنظیم و تهیه این پروژه علمی مساعدت و همکاری نمودند متشکرم.

 

محمد نظری زاده

 

الگوريتم هاي ژنتيک

 Genetic Algorithms

1-1 مقدمه

الگوریتم های ژنتیک یکی از الگوریتم های جستجوی تصادفی است که در ایده آن بر گرفته از طبیعت می باشد.الگوریتم های ژنتیک در حل مسائل بهینه سازی کاربرد دارند.در طبیعت از ترکیب کروموزوم های بهتر،نسل های بهتری پدید می آیند.دراین بین گاهی اوقات جهش هایی نیز در کروموزوم ها روی می دهد که ممکن است باعث بهتر شدن نسل بعدی شوند.الگوریتم ژنتیک نیز با استفاده از این ایده اقدام به حل مسائل می کند.

مختصراً گفته مي شود که الگوريتم ژنتيک (يا GA) يک تکنيک برنامه نويسي است که از تکامل ژنتيکي به عنوان يک الگوي حل نمسئله استفاده مي کند.مسئله اي که بايد حل شود ورودي است و راه حلها طبق يک الگو کد گذاري مي شودتابع fitness هم هر راه حل کانديد را ارزيابي مي کندکه اکثر آنها به صورت تصادفي انتخاب مي شوند.

کلاً اين الگوريتم ها از بخش هاي زير تشکيل مي شوند :

تابع برازش  – نمايش – انتخاب – تغيير

هنگامي كه لغت تنازع بقا به كار مي‌رود اغلب بار ارزشي منفي آن به ذهن مي‌آيد. شايد همزمان قانون جنگل به ذهن برسد و حكم بقاي قوي‌تر!

البته براي آنكه خيالتان راحت شود مي‌توانيد فكر كنيد كه هميشه هم قوي‌ترين‌ها برنده نبوده‌اند. مثلا دايناسورها با وجود جثه عظيم و قوي‌تر بودن در طي روندي كاملا طبيعي بازي بقا و ادامه نسل را واگذار كردند در حالي كه موجوداتي بسيار ضعيف‌تر از آنها حيات خويش را ادامه دادند. ظاهرا طبيعت بهترين‌ها را تنها بر اساس هيكل انتخاب نمي‌كند! در واقع درست‌تر آنست كه بگوييم طبيعت مناسب ترين‌ها (Fittest) را انتخاب مي‌كند نه بهترين‌ها.

قانون انتخاب طبيعي بدين صورت است كه تنها گونه‌هايي از يك جمعيت ادامه نسل مي‌دهند كه بهترين خصوصيات را داشته باشند و آنهايي كه اين خصوصيات را نداشته باشند به تدريج و در طي زمان از بين مي‌روند.

مثلا فرض كنيد گونه خاصي از افراد، هوش بسيار بيشتري از بقيه افراد يك جامعه يا كولوني دارند. در شرايط كاملا طبيعي اين افراد پيشرفت بهتري خواهند كرد و رفاه نسبتا بالاتري خواهند داشت و اين رفاه خود باعث طول عمر بيشتر و باروري بهتر خواهد بود(توجه كنيد شرايط طبيعيست نه در يك جامعه سطح بالا با ملاحظات امروزي يعني طول عمر بيشتر در اين جامعه نمونه با زاد و ولد بيشتر همراه است). حال اگر اين خصوصيت(هوش)ارثي باشد به طبع در نسل بعدي همان جامعه تعداد افراد باهوش به دليل زاد و ولد بيشتر اين‌گونه افراد بيشتر خواهد بود. اگر همين روند را ادامه دهيد خواهيد ديد كه در طي نسل‌هاي متوالي دائما جامعه نمونه ما باهوش و باهوش‌تر مي‌شود. بدين ترتيب يك مكانيزم ساده طبيعي توانسته است در طي چند نسل عملا افراد كم هوش را از جامعه حذف كند علاوه بر اينكه ميزان هوش متوسط جامعه نيز دائما در حال افزايش است(البته امكان داشت اگر داروين بي‌عرضگي افراد باهوش امروزي را مي‌ديد كمي در تئوري خود تجديد نظر مي‌كرد اما اين مسئله ديگريست!).

بدين ترتيب مي‌توان ديد كه طبيعت با بهره‌گيري از يك روش بسيار ساده(حذف تدريجي گونه‌هاي نامناسب و در عين حال تكثير بالاتر گونه‌هاي بهينه) توانسته است دائما هر نسل را از لحاظ خصوصيات مختلف ارتقا بخشد.

البته آنچه در بالا ذكر شد به تنهايي توصيف كننده آنچه واقعا در قالب تكامل در طبيعت اتفاق مي‌افتد نيست. بهينه‌سازي و تكامل تدريجي به خودي خود نمي‌تواند طبيعت را در دسترسي به بهترين نمونه‌ها ياري دهد.

در واقع مي‌توان تكامل طبيعي را به اين‌صورت خلاصه كرد: جست‌وجوي كوركورانه(تصادف يا Blind Search)+ بقاي قوي‌تر.

حال ببينيم كه رابطه تكامل طبيعي با روش‌هاي هوش مصنوعي چيست .هدف اصلي روش‌هاي هوشمند به كار گرفته شده در هوش مصنوعي يافتن پاسخ بهينه مسائل مهندسي ست. بعنوان مثال اينكه چگونه يك موتور را طراحي كنيم تا بهترين بازدهي را داشته باشد يا چگونه بازوهاي يك ربات را محرك كنيم تا كوتاه‌ترين مسير را تا مقصد طي كند(دقت كنيد كه در صورت وجود مانع يافتن كوتاه‌ترين مسير ديگر به سادگي كشيدن يك خط راست بين مبدا و مقصد نيست) همگي مسائل بهينه‌سازي هستند.

 

2-1 الگوريتم ژنتيک چيست؟

الگوريتم هاي ژنتيک از اصول انتخاب طبيعي داروين براي يافتن فرمول بهينه جهت پيش بيني يا تطبيق الگو استفاده مي کنند.الگوريتم هاي ژنتيک اغلب گزينه خوبي براي تکنيک هاي پيش بيني  بر مبناي رگرسيون هستند.همان طور که به این الگوریتم ها ساده،خطي وپارامتريک گفته مي شود،به الگوريتم هاي ژنتيک مي توان غير پارامتريک گفت.

با استفاده از الگوريتم هاي ژنتيک ما يک ابر فرمول يا طرح تنظيم مي کنيم که چيزي شبيه”قيمت نفت در زمان t تابعي از حداکثر 4 متغير است”را بيان مي کند. سپس داده هايي براي گروهي از متغيرهاي مختلف،شايد در حدود 20 متغير فراهم خواهيم کرد.سپس الگوريتم ژنتيک اجرا خواهد شد که بهترين تابع و متغيرها را مورد جستجو قرار مي دهد.روش کار الگوريتم ژنتيک به طور فريبنده اي ساده،خيلي قابل درک وبه طور قابل ملاحظه اي روشي است که ما معتقديم حيوانات آنگونه تکامل يافته اند.هر فرمولي که از طرح داده شده بالا تبعيت کند فردي از جمعيت فرمول هاي ممکن تلقي مي شود خيلي شبيه به اين که بگوييم جرج بوش فردي از جمعيت انسان هاي ممکن است.

متغير هايي که هر فرمول داده شده را مشخص مي کنند به عنوان يکسري از اعداد نشان داده شده اند که معادل دي ان اي آن فرد را تشکيل مي دهند.

موتور الگوريتم ژنتيک يک جمعيت آغاز از فرمول ايجاد مي کند.هر فرد در برابر مجموعه اي از داده ها ي مورد آزمايش قرار مي گيرد و مناسبترين آنها شايد 10 درصد از مناسبترين ها باقي بماند و بقيه کنار گذاشته مي شوند. مناسبترين افراد با هم جفتگيري (جابجايي عناصر دي ان اي) وتغيير (تغيير تصادفي عناصر دي ان اي) کرده اند. مشاهده مي شود که با گذشت از ميان تعدد زيادي از نسلها، الگوريتم ژنتيک به سمت ايجاد فرمول هايي که بيشتر دقيق هستند، ميل مي کند. در حالي که شبکه هاي عصبي هم غير خطي و غير پارامتريک هستند، جذابيت زياد الگوريتم هاي ژنتيک اين است نتايج نهايي قابل ملاحظه ترند. فرمول نهايي براي کاربر انساني قابل مشاهده خواهد بود، و براي ارائه سطح اطمينان نتايج مي توان تکنيک هاي آماري متعارف را بر روي اين فرمول ها اعمال کرد. فناوري الگوريتم هاي ژنتيک همواره در حال بهبود است براي مثال با مطرح کردن معادله ويروس ها که در کنار فرمول ها و براي نقض کردن فرمول هاي ضعيف توليد مي شوند و در نتيجه جمعيت را کلاً قويتر مي سازند. [1]

الگوريتم ژنتيک GA يک تکنيک جستجو در علم کامپيوتر براي يافتن راه حل بهينه و مسائل جستجو است. الگوريتم هاي ژنتيک يکي از انواع الگوريتم هاي تکاملي اند که از علم زيست شناسي مثل وراثت، جهش، انتخاب ناگهاني، انتخاب طبيعي و ترکيب الهام گرفته اند .[2]

عموماً راه حلها به صورت 2 تايي 0و1 نشان داده مي شوند ولي روشهاي نمايش ديگري هم وجود دارد. تکامل از يک مجموعه کاملاً تصادفي از موجوديت ها شروع مي شود و در نسلهاي بعدي تکرار مي شود و در هر نسل مناسبترين ها انتخاب مي شوند و نه بهترين ها.

يک راه حل براي مسئله مورد نظر، با يک ليست از پارامترها نشان داده مي شود که به آنها کروموزوم يا ژنوم مي گويند. کروموزوم ها عموماً به صورت يک رشته ساده از داده ها نمايش داده مي شوند، البته انواع ساختمان داده هاي ديگر هم مي توانند مورد استفاده قرار گيرند. در ابتدا چندين مشخصه به صورت تصادفي براي ايجاد نسل اول توليد مي شوند. در طول هر نسل، هر مشخصه ارزيابي مي شود و ارزش تناسب(fitness) توسط تابع تناسب اندازه گيري مي شود.

گام بعدي ايجاد دومين نسل از جامعه است که بر پايه فرآيندهاي انتخاب، توليد از روي مشخصه هاي انتخاب شده با عملگرهاي ژنتيکي است.

اتصال کروموزوم ها به سر يکديگر و تغيير براي هر فرد، يک جفت والد انتخاب مي شود. انتخابها به گونه اي اند که مناسبترين عناصر انتخاب شوند تا حتي ضعيف ترين عناصر هم شانس انتخاب داشته باشند تا از نزديک شدن به جواب محلي جلوگيري شود. چندين الگوي انتخاب وجود دارد: چرخ منگنه دار(رولت)، انتخاب مسابقه اي (Tournament) ،… .

معمولاً الگوريتم هاي ژنتيک يک عدد احتمال اتصال دارد که بين 0.6و1 است که احتمال به وجود آمدن فرزند را نشان مي دهد. ارگانيسم ها با اين احتمال با هم دوباره با هم ترکيب مي شوند. اتصال 2 کروموزوم فرزند ايجاد مي کند، که به نسل بعدي اضافه مي شوند. اين کارها انجام مي شوند تا اين که کانديدهاي مناسبي براي جواب، در نسل بعدي پيدا شوند. مرحله بعدي تغيير دادن فرزندان جديد است. الگوريتم هاي ژنتيک يک احتمال تغيير کوچک و ثابت دارند که معمولاً درجه اي در حدود 0.01 يا کمتر دارد. بر اساس اين احتمال، کروموزوم هاي فرزند به طور تصادفي تغيير مي کنند يا جهش مي يابند. مخصوصاً با جهش بيتها در کروموزوم ساختمان داده ای که بر رویش کار می نماییم.

اين فرآيند باعث به وجود آمدن نسل جديدي از کروموزوم هايي مي شود، که با نسل قبلي متفاوت است. کل فرآيند براي نسل بعدي هم تکرار مي شود، جفتها براي ترکيب انتخاب مي شوند، جمعيت نسل سوم به وجود مي آيند و … .

اين فرآيند تکرار مي شود تا اين که به آخرين مرحله برسيم.

شرايط خاتمه الگوريتم هاي ژنتيک شامل موارد زیر می باشد:

• به تعداد ثابتي از نسل ها برسيم .
• بودجه اختصاص داده شده تمام شود (زمان محاسبه/پول).
• يک فرد(فرزند توليد شده) پيدا شود که مينيمم (کمترين) ملاک را برآورده کند.
• بيشترين درجه پر ارزش فرزندان حاصل شود يا ديگر نتايج بهتري حاصل نشود.
• بازرسي دستي.
• و یا هر کدام از ترکيبهاي بالا.

 

3-1 ايده اصلي

در دهه هفتاد ميلادي دانشمندي از دانشگاه ميشيگان به نام جان هلند ايده استفاده از الگوريتم ژنتيك را در بهينه‌سازي‌هاي مهندسي مطرح كرد. ايده اساسي اين الگوريتم انتقال خصوصيات موروثي توسط ژن‌هاست. فرض كنيد مجموعه خصوصيات انسان توسط كروموزوم‌هاي او به نسل بعدي منتقل مي‌شوند. هر ژن در اين كروموزوم‌ها نماينده يك خصوصيت است. بعنوان مثال ژن 1 مي‌تواند رنگ چشم باشد ، ژن 2 طول قد، ژن 3 رنگ مو و الي آخر. حال اگر اين كروموزوم به صورت کامل، به نسل بعد انتقال يابد، تمامي خصوصيات نسل بعدي شبيه به خصوصيات نسل قبل خواهد بود. بديهي است كه در عمل چنين اتفاقي رخ نمي‌دهد. در واقع بصورت همزمان دو اتفاق براي كروموزوم‌ها مي‌افتد. اتفاق اول موتاسيون (Mutation) است. موتاسيون به اين صورت است كه بعضي ژن‌ها بصورت كاملا تصادفي تغيير مي‌كنند. البته تعداد اين گونه ژن‌ها بسيار كم مي‌باشد اما در هر حال اين تغيير تصادفي همانگونه كه پيشتر ديديم بسيار مهم است. مثلا ژن رنگ چشم مي‌تواند بصورت تصادفي باعث شود تا در نسل بعدي يك نفر داراي چشمان سبز باشد. در حالي كه تمامي نسل قبل داراي چشم قهوه‌اي بوده‌اند. علاوه بر موتاسيون اتفاق ديگري كه مي‌افتد و البته اين اتفاق به تعداد بسيار بيشتري نسبت به موتاسيون رخ مي‌دهد چسبيدن ابتداي يك كروموزوم به انتهاي يك كروموزوم ديگر است. اين مساله با نام Crossover شناخته مي‌شود. اين همان چيزيست كه مثلا باعث مي‌شود تا فرزند تعدادي از خصوصيات پدر و تعدادي از خصوصيات مادر را با هم به ارث ببرد و از شبيه شدن تام فرزند به تنها يكي از والدين جلوگيري مي‌كند.[1]

در ابتدا تعداد مشخصي از ورودي ها،X₁,X₂,…,X_n که متعلق به فضاي نمونه X هستند را انتخاب مي کنيم و آنها را در يک عدد برداي X=(x1,x2,…xn) نمايش مي دهيم..در مهندسي نرم افزار اصطلاحاً به آنها ارگانيسم يا کروموزوم گفته مي شود.به گروه کروموزوم ها Colony يا جمعيت مي گوييم. در هر دوره Colony رشد مي کند و بر اساس قوانين مشخصي که حاکي از تکامل زيستي است تکامل مي يابند.

براي هر کروموزوم Xi ، ما يک ارزش تناسب(Fitness) داريم که آن را f(Xi) هم مي ناميم. عناصر قويتر يا کروموزوم هايي که ارزش تناسب آنها به بهينه Colony نزديکتر است شانس بيشتري براي زنده ماندن در طول دوره هاي ديگر و دوباره توليد شدن را دارند و ضعيف تر ها محکوم به نابودي اند. به عبارت ديگر الگوريتم ورودي هايي که به جواب بهينه نزديک تراند را نگه داشته و از بقيه صرف نظر مي کند.

يک گام مهم ديگر در الگوريتم، تولد است که در هر دوره يکبار اتفاق مي افتد. محتويات دو کروموزومي که در فرآيند توليد شرکت مي کنند با هم ترکيب ميشوند تا 2 کروموزوم جديد که ما آنها را فرزند مي ناميم  ايجاد کنند. اين هيوريستيک به ما اجازه مي دهد تا 2 تا از بهترين ها را براي ايجاد يکي بهتر از آنها با هم ترکيب کنيم.(evolution)  به علاوه در طول هر دوره، يک سري از کروموزوم ها ممکن است جهش يابند[6](Mutation) .

4-1 الگوريتم

    هر ورودي x در يک عدد برداري X=(x₁,x₂,..,x_n) قرار دارد .براي اجراي الگوريتم ژنتيک مان بايد هر ورودي را به يک کروموزوم تبديل کنيم. مي توانيم اين را با داشتن log(n) بيت براي هر عنصرو تبديل ارزش Xi انجام دهيم مثل شکل زير .

 

 

e(X1)

e(X1)

e(X1)

0111111                   …                 1010111   1111011

(X1, X2,…,Xn)= (123, 87,…, 63)

 

 

 

مي توانيم از هر روش کد کردن براي اعداد استفاده کنيم. در دوره 0، يک دسته از ورودي هاي X را به صورت تصادفي انتخالب مي کنيم. بعد براي هر دوره iام ما ارزش مقدار Fitness را توليد، تغيير و انتخاب را اعمال مي کنيم. الگوريتم وقتي پايان مي يابد که به معيارمان برسيم.

 

 

5-1   سود و کد : 

 

Choose initial population

Repeat

Evaluate the individual fit nesses of a certain proportion of the population

Select pairs of best-ranking individuals to reproduce

Apply crossover operator

Apply mutation operator

Until terminating condition

 

 

6-1 روش هاي نمايش

قبل از اين که يک الگوريتم ژنتيک براي يک مسئله اجرا شود، يک روش براي کد کردن ژنوم ها به زبان کامپيوتر بايد به کار رود. يکي از روش هاي معمول کد کردن به صورت رشته هاي باينري است: رشته هاي 0و1. يک راه حل مشابه ديگر کد کردن راه حل ها در آرايه اي از اعداد صحيح يا اعشاري است، که دوباره هر جايگاه يک جنبه از ويژگي ها را نشان مي دهد. اين راه حل در مقايسه با قبلي پيچيده تر و مشکل تر است. مثلاً اين روش توسط استفان کرمر، براي حدس ساختار 3 بعدي يک پروتئين موجود در آمينو اسيد ها استفاده شد.الگوريتم هاي ژنتيکي که براي آموزش شبکه هاي عصبي استفاده مي شوند، از اين روش بهره مي گيرند.

سومين روش براي نمايش صفات در يک GA يک رشته از حروف است، که هر حرف دوباره نمايش دهنده يک خصوصيت از راه حل است.

خاصيت هر 3 تاي اين روشها اين است که آنها تعريف سازنده ايي را که تغييرات تصادفي در آنها ايجاد مي کنند را آسان مي کنند: 0را به 1 وبرعکس، اضافه يا کم کردن ارزش يک عدد يا تبديل يک حرف به حرف ديگر.

يک روش ديگر که توسط John Koza  توسعه يافت، برنامه نويسي ژنتيک (Genetic programming)است که برنامه ها را به عنوان شاخه هاي داده در ساختار درخت نشان مي دهد. در اين روش تغييرات تصادفي مي توانند با عوض کردن عملگرها يا تغيير دادن ارزش يک گره داده شده در درخت، يا عوض کردن يک زير درخت با ديگري به وجود آيند.

 

8-1 روش هاي انتخاب

روش هاي مختلفي براي الگوريتم هاي ژنتيک وجود دارند که مي توان براي انتخاب ژنوم ها از آنها استفاده کرد. اما روش هاي ليست شده در پايين از معمولترين روش ها هستند.

انتخاب Elitist : مناسبترين عضو هر اجتماع انتخاب مي شود.

انتخاب Roulette : يک روش انتخاب است که در آن عنصري که عدد برازش(تناسب) بيشتري داشته باشد، انتخاب مي شود.

انتخاب Scaling : به موازات افزايش متوسط عدد برازش جامعه، سنگيني انتخاب هم بيشتر مي شود و جزئي تر. اين روش وقتي کاربرد دارد که مجموعه داراي عناصري باشد که عدد برازش بزرگي دارند و فقط تفاوت هاي کوچکي آنها را از هم تفکيک مي کند.

انتخاب Tournament : يک زير مجموعه از صفات يک جامعه انتخاب مي شوند و اعضاي آن مجموعه با هم رقابت مي کنند و سرانجام فقط يک صفت از هر زير گروه براي توليد انتخاب مي شوند.

بعضي از روشهاي ديگر عبارتند از:Rank Selection, Generational Selection, Steady-State Selection .Hierarchical Selection

9-1 روش هاي تغيير

وقتي با روش هاي انتخاب کروموزوم ها انتخاب شدند ، بايد به طور تصادفي براي افزايش تناسبشان اصلاح شوند. 2 راه حل اساسي براي اين کار وجود دارد. اولين و ساده ترين جهش (Mutation) ناميده مي شود. درست مثل جهش در موجودات زنده که عبارت است از تغيير يک ژن به ديگري، در الگوريتم ژنتيک جهش تغيير کوچکي در يک نقطه از کد خصوصيات ايجاد مي کند.

دومين روش Crossover نام دارد و 2 کروموزوم براي معاوضه سگمنتهاي کدشان انتخاب مي شوند. اين فرآيند بر اساس فرآيند ترکيب کروموزوم ها در طول توليد مثل در موجودات زنده شبيه سازي شده. اغلب روش هاي معمول Crossover شامل Single-point Crossoverهستند، که نقطه تعويض در جايي تصادفي بين ژنوم ها است. بخش اول قبل از نقطه، و بخش دوم سگمنت بعد از آن ادامه پيدا مي کند، که هر قسمت برگرفته از يک والد است،که 50/50 انتخاب شده.

شکل هاي بالا تاثير هر يک از عملگر هاي ژنتيک را روي کروموزوم هاي 8 بيتي نشان مي دهد. شکل بالاتر 2 ژنوم را نشان مي دهد که نقطه تعويض بين 5امين و 6امين مکان در ژنوم قرار گرفته، ايجاد يک ژنوم جديد از پيوند اين 2 والد بدست مي آيند. شکل دوم ژنومي را نشان مي دهد که دچار جهش شده و 0 در آن مکان به 1 تبديل شده.

 

10-1 تقاط قوت الگوريتم هاي ژنتيک

اولين و مهمترين نقطه قوت اين الگوريتم ها اين است که الگوريتم هاي ژنتيک ذاتاً موازي اند. اکثر الگوريتم هاي ديگر موازي نيستند و فقط مي توانند فضاي مسئله مورد نظر را در يک جهت در يک لحظه جستجو کنند و اگر راه حل پيدا شده يک جواب بهينه محلي باشد و يا زير مجموعه اي از جواب اصلي باشد بايد تمام کارهايي که تا به حال انجام شده را کنار گذاشت و دوباره از اول شروع کرد. از آنجايي که GA چندين نقطه شروع دارد، در يک لحظه مي تواند فضاي مسئله را از چندجهت مختلف جستجو کند. اگر يکي به نتيجه نرسيد ساير راه ها ادامه مي يابند و منابع بيشتري را در اختيار شان قرار مي گيرد.در نظر بگيريد: همه 8 عدد رشته باينري يک فضاي جستجو را تشکيل مي دهند،که مي تواند به صورت ******** نشان داده شود. رشته 01101010 يکي از اعضاي اين فضاست. همچنين عضوي از فضاهاي *******0و******01و0 ******0و*1*1*1*0و 0**01*01 والي آخر باشد.

به دليل موازي بودن واين که چندين رشته در يک لحظه مورد ارزيابي قرار مي گيرند GA ها براي مسائلي که فضاي راه حل بزرگي دارند بسيار مفيد است. اکثر مسائلي که اين گونه اند به عنوان “غير خطي” شناخته شده اند. در يک مسئله خطي،Fitness هر عنصر مستقل است، پس هر تغييري در يک قسمت بر تغيير و پيشرفت کل سيستم تاثير مستقيم دارد. مي دانيم که تعداد کمي از مسائل دنياي واقعي به صورت خطي اند. در مسائل غير خطي تغيير در يک قسمت ممکن است تاثيري ناهماهنگ بر کل سيستم و يا تغيير در چند عنصر تاثير فراواني بر سيستم بگذارد. خوشبختانه موازي بودن GA باعث حل اين مسئله مي شود و در مدت کمي مشکل حل مي شود. مثلاً براي حل يک مسئله خطي 1000 رقمي 2000 امکان حل وجود دارد ولي براي يک غير خطي 1000 رقمي  2¹⁰⁰⁰ امکان .

يکي از نقاط قوت الگوريتم هاي ژنتيک که در ابتدا يک کمبود به نظر مي رسد اين است که :GA ها هيچ چيزي در مورد مسائلي که حل مي کنند نمي دانند و اصطلاحاً به آنهاBlind Watchmakers مي گوييم. آنها تغييرات تصادفي را در راه حل هاي کانديدشان مي دهند و سپس از تابع برازش براي سنجش اين که آيا آن تغييرات پيشرفتي ايجاد کرده اند يا نه، استفاده مي کنند. مزيت اين تکنيک اين است که به GA اجازه مي دهند يا با ذهني باز شروع به حل کنند. از آنجايي که تصميمات آن اساساً تصادفي است، بر اساس تئوري همه راه حلهاي ممکن به روي مسئله باز است،ولي مسائلي که محدود به اطلاعات هستند بايد از راه قياس تصميم بگيرند و در اين صورت بسياري از راه حلهاي نو و جديد را از دست مي دهند.

يکي ديگر از مزاياي الگوريتم ژنتيک اين است که آنها مي توانند چندين پارامتر را همزمان تغييردهند. بسياري ازمسائل واقعي نمي توانند محدود به يک ويژگي شوند تا آن ويژگي ماکسيمم شود يا مينيمم و بايد چند جانبه در نظر گرفته شوند.GA ها در حل اين گونه مسائل بسيار مفيدند و در حقيقت قابليت موازي کار کردن آنها اين خاصيت را به آنها مي بخشد و ممکن است براي يک مسئله 2 يا چند راه حل پيدا شود، که هر کدام با در نظر گرفتن يک پارامتر خاص به جواب رسيده اند.

 

محدوديتهای GAها

يک مشکل چگونگي نوشتن عملگر Fitness است که منجر به بهترين راه حل براي مسئله شود. اگر اين کارکرد برازش به خوبي و قوي انتخاب نشود ممکن است باعث شود که راه حلي براي مسئله پيدا نکنيم يا مسئله اي ديگر را به اشتباه حل کنيم. به علاوه براي انتخاب تابع مناسب براي Fitness ،پارامترهاي ديگري مثل اندازه جمعيت، نرخ جهش وCrossover ،قدرت ونوع انتخاب هم بايد مورد توجه قرار گيرند.

مشکل ديگر، که آن را نارس مي ناميم اين است که اگر يک ژنوم که فاصله اش با ساير ژنوم هاي نسل اش زياد باشد(خيلي بهتر از بقيه باشد) و خيلي زود ديده شود(ايجاد شود) ممکن است محدوديت ايجاد کند و راه حل را به سوي جواب بهينه محلي سوق دهد. اين اتفاق معمولاً در جمعيت هاي کم اتفاق مي افتد. روش هاي Rank ,Scaling   tournament selection بر اين مشکل غلبه مي کنند.[3]

12-1 چند نمونه از کاربرد هاي الگوريتم هاي ژنتيک

نرم‌افزار شناسايي چهره با استفاده از تصوير ثبت شده به همت مبتکران ايراني طراحي و ساخته شد. در اين روش، شناسايي چهره براساس فاصله اجزاي چهره و ويژگي‌هاي محلي و هندسي صورت مي‌گيرد که تغييرات ناشي از گيم، تغييرات نور و افزايش سن کمتين تأثير را خواهد داشت.

همچنين گراف‌ها براي چهره‌هاي جديد با استفاده از الگويتم‌هاي ژنتيک ساخته شده و با استفاده از يک تابع تشابه، قابل مقايسه با يکديگر هستند که اين امر تأثير به‌سزايي در افزايش سرعت شناسايي خواهد داشت که در زیر تعدادی از آنها را نام می برده ایم.

توپولوژي هاي شبکه هاي کامپيوتي توزيع شده

بهينه سازي ساختار ملکولي شِميايي (شيمي)

مهندسي برق براي ساخت آنتنهاي Crooked-Wire Genetic Antenna

مهندسي نرم افزار

بازي هاي کامپيوتري

مهندسي مواد

مهندسي سيستم

رباتيک(Robotics)

تشخيص الگوو استخراج داده(Data mining)

حل مسئله فروشنده دوره گرد

آموزش شبکه هاي عصبي مصنوعي

ياددهي رفتار به رباتها با GA

يادگيري قوانين فازي با استفاده از الگويتم هاي ژنتيک

 

13-1 نگاهی ریزتر بر پردازش تکاملی و الگوريتمهای ژنتيک
مقدمه

با نظر به اينكه وسعت و محدوده الگوريتمهاي ژنتيك بسيار گسترده مي باشد، لذا پوشش دادن تمامي مطالب در اين صفحات امكانپذير نمي باشد. اما در حد امكان الگوريتمهاي ژنتيك را با بکارگيری مراجع شرح داده و توضيح مي دهيم كه براي چه اهدافي سودمند مي باشند. الگوريتمهاي ژنتيك بخشي از تحولات رشته كامپيوتر هستند كه داراي فضاي رشد سريعي در عرصه هوش مصنوعي مي باشند.

به طوري كه مي توان حدس زد، الگوريتمهاي ژنتيك از تئوري داروين كه در مورد تكامل تدريجي است، الهام گرفته اند. با نگاه دقيق به روند تكامل، يعني روندي كه طبيعت براي حل مسائل خود از آن استفاده مي كند، مي توان به ايده هاي جالب و قابل پياده سازي رسيد. جانوران براي ابقاء خود و ادامه حيات مجبور به سازگاري با محيط هستند. اطلاعات گرفته شده درطي هزاران سال از طبيعت در كروموزومها ودر سطح پايين تر روي ژن ها و دي ان آ ها ذخيره مي گردد.

تاريخچه

انديشه تكامل در رشته كامپيوتر و محاسبات تكاملي در سال 1960 توسط   I-Rechenbergدر اثر خود بنام فنون تكامل معرفي گشت. انديشه او بعدها توسط محققان ديگري توسعه داده شد. الگوريتمهاي ژنتيك توسط شخصي بنام John Holland بوجود آمد و بعد توسط خود او و شاگردانش توسعه يافت. اين مراحل منتهي به يك كتاب بنام“ سازش بين سيستمهاي طبيعي و مصنوعي” از آقاي Holland  شد كه در سال 1975 منتشر گشت.

در سال 1992 آقاي  John koza الگوريتم ژنتيك را براي ايجاد برنامه هايي در جهت انجام وظايفي معين بكار برد. او روش خود را برنامه نويسي ژنتيك[1] ( GP) ناميد. اكثر برنامه ها براي اين الگوريتمها با زبان LISP  نوشته مي شوند، چون برنامه ها در اين زبان مي توانند بشكل يك درخت تجزيه بيان شوند و درخت تجزيه هم شيئي است كه الگوريتمهاي ژنتيك روي آن كار مي كنند.

کروموزوم

تمام تركيب بدن موجودات زنده از سلول تشكيل شده است. درهر سلول مجموعه يكساني ازكروموزومها وجود دارند. كروموزومها رشته اي از DNA هستند و به عنوان يك مدل سازي براي تركيب كامل بدن موجود زنده انجام وظيفه مي نمايند. يك كروموزوم شامل ژنها مي باشد كه بلوكهايي از DNA  هاست. هر ژن يك پروتئين ويژه را به رمز در مي آورد، يعني رمزگذاري مي كند. اساساً باينصورت مي تواند بيان شود كه هر ژن يك ويژگي و نشان ويژه را به رمز در مي آورد، براي مثال رنگ چشمها.

در طبيعت، گوناگوني موجودات از طريق گوناگوني در كروموزومهاي موجودات ايجاد مي‏شود. درجريان توليدمثل،‌ ابتدا آميزش صورت مي گيرد(برش[2]) و ژنها توسط والدين به چندين طريق مختلف بصورت كروموزومهاي جديد و سالم تشكيل مي شوند. سپس اين كروموزومهاي ايجاد شده جديد مي توانند تغيير داده شوند(جهش[3]). جهش به اين معني است كه عناصر DNA يك ذره قابل تغيير هستند. اين تغييرات در اصل در زمان كپي كردن ژنها از طرف والدين ايجاد مي شوند. ميزان شايستگی[4] يك تركيب موجود زنده به اين معني است كه موجود زنده در طول عمرش به چه ميزان موفق و كامياب خواهد بود. موجوداتي كه به نحو بهتري اعمال حياتي خود را در محيط زيست شان انجام مي دهند، سازگارتر هستند و با نرخ بيشتري توليد مثل مي كنند. موجودات با سازگاري كمتر شانس كمتري براي ادامه حيات دارند و اگر بتوانند توليدمثل كنند، با نرخ كمتري اين كار را انجام مي دهند.

به اينگونه تغييرات قابل مشاهده و اندازه گيري، تكامل گفته مي شود. نشان داده شده است كه فراروند تكامل مي تواند در سيستمهاي مصنوعي ساخت بشر بكار برده شود. بطوريكه مي توان هر مسئله اي را در تكامل با مفاهيم ژنتيكي بيان كرد. بعد از بيان مسئله، مي توان آن را بوسيله الگوريتم ژنتيك حل كرد.

براي حل مسئله به كمك الگوريتم ژنتيك، ابتدا بايد نحوه نمايشي را بيابيم به نحوي كه هر كروموزوم يك راه حل مسئله را مشخص كند. نحوه نمايش مي تواند بطور مستقيم بر كارآيي الگوريتم ژنتيك تأثير گذار باشد.

فضای جستجو

زمانيكه مي خواهيم برخي مسائل را حل كنيم، معمولا در جستجوي راه حلهايي هستيم كه بهتر و بهينه تر از بقيه باشند. فضاي تمامي راه حلهاي ممكن، فضاي جستجو ناميده مي شود. هر نقطه در فضاي جستجو يك راه حل ممكن و امكانپذير را نشان مي دهد. هر راه حل بر حسب مقادير مختلف مثل ميزان برازندگي مشخص مي شود. جستجوي يك راه حل برابر است با جستجوي يك مقدار حداقل يا حداكثر در فضاي جستجو. در اينجا مشكل اين است كه عمل جستجو مي تواند بسيار پيچيده باشد. معمولا فرد نمي داند كه كجا را براي راه حل جستجو كند و يا از كجا شروع كند. روشهاي بسياري براي يافتن راه حلهاي مناسب( نه لزوما بهترين راه حل ) موجود هستند كه يكي از آنها استفاده از الگوريتمهاي ژنتيك مي باشد. فضاي جستجو در الگوريتمهاي ژنتيكي را جمعيت ژنتيكي مي‏نامند.

معيت ژنتيکی

الگوريتم با مجموعه اي از راه حلها كه توسط كروموزومها نمايش داده مي شوند، آغاز مي شود كه اين مجموعه، جمعيت ژنتيكي نام دارد. راه حلها از يك جمعيت ژنتيكي برداشته ميشوند و براي تشكيل يك جمعيت ژنتيكي جديد بكار مي روند. مزيت اين كار آن است كه جمعيت جديد نسبت به جمعيت قبلي بهتر خواهد بود. پس جمعيت ژنتيكي متشكل از كروموزومهاست. تعداد كروموزومها در جمعيت ژنتيكي محدود بوده و از يك تعداد حداكثر نمي تواند بيشتر شود. انتخاب كروموزومها براي ايجاد جمعيت جديد بر حسب شايستگي آنها مي باشد. كروموزومهاي با شايستگي بالا فرصت زيادي براي تكثير دارند و بر اثر رقابت، كروموزومهايي كه داراي شايستگي بالا هستند، در جمعيت باقي مي مانند و به تكثير و توليد مي پردازند. اين عمل تا زماني تكرار مي شود كه بعضي شرطها حصول گردد. براي مثال، تعداد جمعيت هاي ژنتيكي و يا پيشرفتهاي بهترين راه حل مي تواند مدنظر باشد.

 

تابع شايستگی

شانس كروموزومها براي ادامه حيات براساس ميزان شايستگي آنها تعيين ميشود. يعني كروموزومهايي كه ميزان برازندگي بالايي دارند، شانس بيشتري براي ادامه حيات و توليدمثل خواهند داشت. لذا براي مشخص كردن اينكه پاسخ ها تا چه حد مناسب هستند، از تابع برازندگي استفاده ميشود. اين تابع يك كروموزوم را دريافت كرده و و عددي را بعنوان خروجي بر مي گرداند. اين عدد ميزان شايستگي كروموزوم بعنوان يك راه حل را نشان خواهد داد.

عملگرهای ژنتيک

به مجموعه اعمالي كه در الگوريتم ژنتيك استفاده مي شود تا از روي جمعيت فعلي، جمعيت بعدي ساخته شود،‌ عملگرهاي ژنتيك گفته مي شود. همواره كروموزومها از ميان نسل فعلي برحسب ميزان برازندگي شان انتخاب مي شوند، سپس عملگرهاي ژنتيك روي آنها انجام مي گيرند و بعد به جمعيت جديد انتقال مي يابند. اولين مرحله در ساخت كروموزومها، رمزگذاري كروموزوم مي باشد. متداولترين روش رمزگذاري كه مورد استفاده قرار مي گيرد، رمزگذاري باينري نام دارد. مثلا كروموزوم مي تواند بصورت زير باشد :

11011001001110110

در اين نوع نمايش، هر كروموزوم داراي يك رشته باينري است كه اساساً وابسته به مسئله حل شده است. اولين سؤال اين است كه كروموزومها چگونه ساخته مي شوند و نوع رمزگذاري چگونه انتخاب ميشود. براي اين كار، برش و جهش بعنوان دو عملگر پايه براي الگوريتم ژنتيک مطرح مي شوند. سؤال بعدي چگونگي انتخاب والدين براي برش  است. اين كار مي تواند با روشهاي زيادي انجام گيرد. اما مقصود اصلي، انتخاب بهترين والدين است ( به اين اميد كه بهترين والدين، بهترين اولاد را توليد خواهند كرد) بعلاوه ممكن است شما فكر كنيد كه ساخت جمعيت جديد توسط فقط اولاد جديد مي تواند باعث گم شدن بهترين كروموزوم از جمعيت اخير شود، درست است، از اينرو اغلب از تكنيك Ellitism  استفاده مي شود. عمل Ellitism  به اين معني است كه حداقل يك راه حل يا كروموزوم بدون تغيير يافتن در يك جمعيت جديد كپي مي شود. بنابراين بهترين راه حل يافت شده، ميتواند تا پايان اجرا باقي بماند. پس در اين عمل ژنتيكي يك كروموزوم از ميان نسل فعلي انتخاب شده و عينا به نسل بعدي منتقل مي شود.

 

عملگر برش

بعد از انتخاب نوع رمزگذاري، ميتوان يك گام در جهت برش برداشت. در اين عمل، ژنها از كروموزومهاي والدين انتخاب شده و يك فرزند جديد ايجاد ميشود. ساده ترين راه انجام آن، انتخاب تصادفي دو نقطه برش  و كپي عيني تا آن نقطه از والدين اول و بعد كپي عيني از نقطه برش به بعد از والدين دوم مي باشد. با اين عمل،‌ تركيبهاي مختلف ژن هاي موجود در  جمعيت فعلي ساخته ميشود.

برش ميتواند بصورت زير باشد:

Chromosome1          11011  |  00100110110                                     

Chromosome2          11011 | 11000011110                                       

 

Offspring1          11011  |  11000011110                                     

Offspring2         11011  |  00100110110                                   

 

راههاي ديگري هم براي انجام عمل برش وجود دارند. براي مثال ميتوانيم نقاط برش بيشتري انتخاب كنيم. برش  ميتواند بسيار پيچيده شود و به ميزان زيادي وابسته به نوع رمزگذاري كروموزوم است.

عملگر جهش

بعد از اجراي يك برش، عمل جهش بايد انجام گيرد. جهش بمعني پيشگيري از ميل كردن تمامي راه حلهاي جمعيت ژنتيكي بسوي يك مقدار ثابت مي باشد. جهش بطورتصادفي اولاد جديدرا تغيير ميدهد. در رمزگذاري باينري ميتوانيم تعداد كمي از بيتهاي تصادفي را از1   به 0  و يا  از 0  به 1  تبديل كنيم. جهش ميتواند بصورت زير باشد:

Original Offspring1          1101111000011110

Original Offspring2          1101100100110110

Mutated Offspring1          1100111000011110

Mutated Offspring2          1101101100110110

جهش هم مانند برش وابسته به نوع رمزگذاري است. در عمل جهش كروموزومهاي جديدي ساخته ميشوند كه در آن تركيبهاي جديدي از ژنها وجود داردكه قبلا در جمعيت ژنتيكي وجود نداشته است. پس عمل جهش در واقع تأمين كننده نياز الگوريتم ژنتيك به تنوع و گوناگوني كروموزومهاي جامعه است. اين عملگر باعث ميشود تا تنوع از بين رفته در نسلهاي قبلي جبران شود. عمل جهش از رسيدن مقادير برازندگي تمامي كروموزومهابه سوي يك مقدار ثابت جلوگيري مي كند  تا انتخاب كروموزومها مشكل نشود.

 

پارامترهای الگوريتم ژنتيک 

 دو پارامتر اصلي در الگوريتم ژنتيك موجودند كه عبارتند از:

احتمال برش و احتمال جهش

پارامتر احتمال برش بيان مي كند كه چه اوقاتي عمل برش انجام خواهد گرفت. اين احتمال بصورت درصد بيان ميشود. درصورتيكه هيچ برشی وجود نداشته باشد، فرزند يك كپي عيني از والدين خواهد بود و اگر برش وجود داشته باشد، فرزندان از بخشهاي كروموزوم والدين ساخته ميشوند. اگر احتمال برش %100 باشد، آنگاه تمامي فرزندان بوسيله برش ساخته ميشوند و در صورتيكه اين احتمال صفر درصد  باشد، تمام توليدات جديد از كپي عيني كروموزومها در جمعيت قبلي بوجود مي آيند. برش به اين اميد انجام مي گيرد كه كروموزومهاي جديد، بخشهاي سودمند كروموزومهاي قبل را خواهند داشت و احتمالاً كروموزومهاي جديد بهتر هم خواهند بود. بهرحال دست كشيدن از بعضي قسمتهاي جمعيت قبلي در توليد بعدي سودمند است.

پارامتر احتمال جهش بيان مي كند كه چه اوقاتي، بخشهايي از كروموزومها تغيير داده ميشوند. اگر هيچ جهشی  وجود نداشته باشد، فرزندان بدون هيچ تغييري بعد از عمل برش حاصل ميشوند و درصورتيكه جهش انجام گيرد، بخشي از كروموزومها تغيير داده ميشوند. اگر احتمال جهش %100 باشد، تمامي كروموزومها تغيير داده ميشوند و در صورتيكه اين احتمال صفر درصد باشد، هيچ كدام از كروموزومها تغيير داده نمي شوند. عمل جهش اغلب اوقات نبايد اتفاق بيافتد، چون در صورت زياد بودن عمل جهش، الگوريتم ژنتيكي به يك جستجوي تصادفي تغيير خواهد يافت.

پارامترهاي ديگري نيز براي الگوريتمهاي ژنتيكي موجودند. يكي از پارامترهاي مهم ديگر، سايز جمعيت ژنتيكي است. سايز جمعيت، حداكثر تعداد كروموزومها را در يك جمعيت ژنتيكي مشخص مي كند. اگر كروموزومهاي خيلي كمي وجود داشته باشند، الگوريتم ژنتيك امكانات كمي براي اجراي برش خواهد داشت و تنها يك قسمت كوچك از فضاي جستجو كاوش خواهد گرديد. از طرف ديگر، اگر كروموزومهاي زيادي موجود باشند، سرعت الگوريتم ژنتيك كم خواهد شد. تحقيقات نشان ميدهد كه بدليل برخي محدوديتها ( كه به نوع رمزگذاري و مسأله وابسته است) استفاده از جمعيت بسيار بزرگ سودمند نيست، چون باعث حل سريعتر مسأله نميشود. پارامتر بعدي، تعداد نسلهاست و حداكثر تعداد نسل هايي را كه توسط الگوريتم ژنتيك توليد ميشوند را مشخص مي كند.

6-9) ساختار کلی الگوريتمهای ژنتيک

براي ساخت يك الگوريتم ژنتيك، تعدادي مراحل وجود دارد كه ملزم به انجامشان مي باشيم و عبارتند از:

• [start] : جمعيتي تصادفي متشكل از N  كروموزوم را بصورت تصادفي توليد مي كند. يعني راه حلهاي مناسب براي مسأله را توليد مي نمايد.

2- [Fitness]: ارزيابي برازندگي براي هر كروموزوم  x در جمعيت ژنتيكي توسط تابع f(x) .

3-[New population] : يك جمعيت جديد را ايجاد مي كند و گامها را تا كامل شدن جمعيت جديد نشان ميدهد.

4-[Selection]  : دو كروموزوم والدين را از يك جمعيت بر پايه برازندگيشان انتخاب مي كند. ( بهترين برازندگي، شانس بيشتري براي انتخاب دارد ).

5-[Crossover]  : با يك احتمال برش، اولاد جديد از روي والدين تشكيل ميشوند.

6-[Mutation]  : با يك احتمال جهش، اولاد جديد از هر مكاني قابل تغيير هستند.

7-[Accepting]  : قرار دادن اولاد جديد در يك جمعيت جديد.

8-[Replace]  : بكار بردن جمعيت توليد شده جديد براي اجراي مجدد الگوريتم.

9-[Test]  : اگر شرط نهايي برآورده شود، الگوريتم متوقف ميشود و بهترين راه حل كه در جمعيت جاري است، برگردانده ميشود.

10-[Loop]  : رفتن به گام دوم.

اين ساختار در شکل (6-1) نيز ديده می شود.

(شکل6-1) ساختار کلی الگوريتم ژنتيک 

6-10) شرط خاتمه الگوريتمهای ژنتيک

اين نوع الگوريتم نيز مانند هر الگوريتم ديگري بايد داراي شرط خاتمه باشد. اين شرط مي تواند يكي از شروط زير باشد:

1- ايجاد حداكثر N  نسل توسط الگوريتم ژنتيك.

2- گذشت زمان T  از شروع اجراي الگوريتم ژنتيك.

3- ايجاد چند نسل متوالي بطوريكه در اين چند نسل هيچ كروموزوم بهتري ايجاد نشود.

4- بزرگتر يا مساوي شدن برازندگي يكي از كروموزومها از يك مقدار آستانه.

6-11) انواع روشهاي رمزگذاري كروموزوم

راه هاي زيادي براي انجام اين كار وجود دارد، اما راهي كه انتخاب مي كنيم بايد مناسب براي مسأله اي باشد كه مي خواهيم حل كنيم. برخي از گونه هاي نمايش بصورت زير هستند:

• نمايش باينري- نمايش يك عضو مي تواند با استفاده از مقادير 0  يا  1   صورت گيرد. رمزگذاري باينري متعارفترين نوع رمزگذاري است، چون بطور عمده اولين مسائل در باب  GA  از اين نوع رمزگذاري كروموزوم استفاده كرده اند. در اين روش كروموزوم بصورت زير نمايش داده ميشود:

1010101011110011

• نمايش با مقدار حقيقي- اگر راه حلي كه ما در جستجوي آن هستيم، ليستي از اعداد حقيقي باشد، آنگاه يك رمزگذاري بسيار طبيعي بصورت يك ليست از اعداد حقيقي خواهد بود، نه بصورت رشته اي از صفرها و يك ها.
• نمايش ترتيبي- اين نوع نمايش براي مسائل مرتب سازي يا ترتيبي بكار ميرود. مثال مشهور: مسأله فروشنده دوره گرد كه در آن هر شهر يك مقدار يكتا از 1 تا  N دارد. يك راه حل مي تواند بصورت (5,4,2,1,3)  باشد.
• نمايش درختي- در اين نوع نمايش، اعضا در جمعيت بصورت درخت مي باشند. هر عبارت مي تواند بصورت درختي از توابع و پايانه ها رسم شود. اين توابع و پايانه ها مي توانند هر چيزي باشند.

مثال:

توابع:  sine ,  add ,  sub  ,  and و…

پايانه ها : x , y , true , false  و…

اين نوع رمزگذاري اساسا براي برنامه هاي استنتاجي و برنامه هاي ژنتيكي بكارميرود. زبان برنامه نويسيLISP  اغلب اين نوع را بكار مي برد، چون برنامه ها در اين زبان به اين شكل نمايش داده ميشوند و مي توانند

به آساني بصورت يك درخت، تجزيه شوند. از اينرو اعمال برش و جهش مي توانند نسبتاً به آساني انجام گيرند.kershenbaum  (1997) پنج خصوصيت را شناسايي كرد كه براي رمزگذاري دلخواه مورد نياز هستند و عبارتند از:

• آن بايد تمامي راه حلهاي امكانپذير را نمايش دهد.
• بايد قادر باشد تا فقط راه حلهاي امكانپذير را نمايش دهد.
• تمام راه حلهاي امكانپذير بايد يك احتمال يكسان براي نمايش داده شدن داشته باشند.
• بايد روش سودمندي را با يك تعداد كمي از ژنها نمايش دهد.
• رمزگذاري بايد داراي مكان باشد. به اين مفهوم كه تغييرات كوچك درآن مكان كروموزوم، تغييرات كوچكي را در راه حل ايجاد نمايد.

اگر چه بعضي از اين خصوصيات در تضاد با يكديگرند، اما آنها راهبرد سودمندي را در انتخاب يك روش رمزگذاري ارائه مي دهند.

پس از انتخاب نحوه نمايش و رمزگذاري و ايجاد كروموزومها، آنها را بايد مقداردهي نمود.

6-12) انواع روشهای انتخاب

بطوريكه ديده شد، كروموزومها از جمعيت ژنتيكي انتخاب ميشوند تا بعنوان والدين براي عمل برش بكار روند. مسأله اين است كه اين كروموزومها چگونه انتخاب ميشوند. مطابق با تئوري داروين، بهترين كروموزومها بايد زنده بمانند و اولاد جديد را ايجاد نمايند. براي انتخاب بهترين كروموزومها، روشهاي زيادي وجود دارند. چند نمونه ازآنها عبارتند از:

1. Roulette wheel selection
2. Boltzman selection
3. Tournament selection
4. Rank selection
5. Steady State selection

 

بعضي از اين روشها را در ادامه توضيح مي دهيم.

Roulette Wheel Selection : در اين روش، والدين بر طبق شايستگي شان (ميزان Fitness  ) انتخاب ميشوند. بهترين كروموزومها آنهايي هستند كه فرصت وشانس بيشتري براي انتخاب شدن دارند. در اين روش كروموزومها روي چرخ قرار داده ميشوند و بر طبق مقادير برازندگيشان مكاني از چرخ را اشغال مي نمايند. سپس چرخ، چرخانده ميشود و بعد از توقف، كروموزوم مشخص شده انتخاب ميشود، بديهي است كه كروموزوم با ميزان برازندگي بيشتر متعدداً انتخاب خواهد گرديد.

Rank Selection :  زمانيكه مقادير برازندگيها اختلاف زيادي دارند، روش انتخاب قبلي داراي مشكلاتي خواهد بود. براي مثال اگر شايستگي بهترين كروموزوم در روش قبلي %90 باشد، در اينصورت كروموزومهاي ديگر شانس خيلي كمي براي انتخاب شدن خواهند داشت. روش  Rank در ابتدا، جمعيت ژنتيكي رادسته بندي مي كند و سپس هر كروموزوم، يك مقدار برازندگي را از اين دسته بندي به خود مي گيرد. در بدترين حالت، مقدار برازندگي برابر 1 خواهد بود و بعد 2 و …. و بهترين برازندگي برابر با مقدار  N خواهد بود كه  N تعداد كروموزومها در جمعيت است. در اينصورت تمامي كروموزومها يك فرصت و شانس براي انتخاب شدن خواهند داشت. اما عيب اين روش آن است كه مي تواند به همگرايي كند و آهسته اي منتهي شود، چون بهترين كروموزومها اختلاف زيادي با همديگر نخواهند داشت.

Steady State Selection : اين روش ويژه انتخاب والدين نمي باشد. عملكرد اصلي اين نوع انتخاب آن است كه قسمت بزرگي از كروموزومها بايد در توليدها و نسلهاي بعدي زنده بمانند. سپس توسط الگوريتم ژنتيك در هر نسل تعداد كمي كروموزوم با برازندگي بالا براي ساخت يك فرزند جديد انتخاب ميشود. بعد برخي از كروموزومها با برازندگي كم كنار گداشته ميشوند و اولاد جديد به جاي آنها قرار مي‏گيرند. باقيمانده جمعيت براي توليد بعدي باقي مي ماند.

Tournament Selection : در اين روش  K كروموزوم بطور تصادفي از درون جمعيت انتخاب ميشوند كه  K  عددي ثابت است. سپس از بين اين  K كروموزوم انتخاب شده، بهترين آنها از نظر ميزان برازندگي برداشته ميشود. شکل (6-2) را ببينيد. k سايز ‏ Tournament ناميده ميشود.

 

(شکل6-2) روش انتخاب Tournament 

انواع روشهای عمل برش

در رمزگذاري باينري دو نوع برش داريم: تك نقطه اي و دو نقطه اي.

در روش تك نقطه اي، يك نقطه برش انتخاب ميشود. رشته باينري از شروع تا نقطه برش از يكي از والدين كپي ميشود و بعد بقيه آن از والدين دوم كپي ميشود. بصورت زير:

در روش دو نقطه اي، دو نقطه برش انتخاب ميشود. رشته باينري از شروع كروموزوم تا نقطه برش اول از يكي از والدين كپي ميشود و بعد رشته باينري از نقطه اول تا نقطه برش دوم از والدين دوم كپي ميشود و سپس بقيه از مابقي  والدين اول برداشته ميشود. شکل (6-3) را ببينيد.

(شکل 6-3)- عملگر برش 

 

برش متحدالشكل: در اين روش بيتها بصورت تصادفي از والدين اول يا دوم كپي ميشوند.

برش حسابي: چندين عملگرحسابي براي ساخت يك فرزند جديد انجام مي گيرد.

در رمزگذاري نوع ترتيبي نيز انواع تك نقطه اي و چند نقطه اي را داريم.

برش درختي: با اين روش در هر دو والدين، يك نقطه برش انتخاب مي گردد و والدين در اين نقطه تقسيم مي شوند و قسمت پايين برش  را براي توليد فرزند جديد تعويض مي كنند.

انواع روشهای عمل جهش

نكته مهم اين است كه عمل جهش بايد كروموزومهاي معتبري را توليد نمايد. در جهش باينري مطابق شکل (6-4) بعضي از بيتها بصورت تصادفي انتخاب شده و از  0  به  1 يا از  1  به 0   تبديل ميشوند.

(شکل 6-4) عملگرجهش روی نمايش باينری 

در جهش ترتيبي مطابق شکل (6-5) دو ژن مختلف بصورت تصادفي انتخاب شده و تعويض مي‏گردند.

(شکل 6-5) عملگرجهش  روی نمايش ترتيبی

 

درجهش براي نمايش درختي، يك گره را انتخاب كرده و آن را با يك گره همانند ديگر جايگزين مي كند. بصورت شکل (6-6).

 

(شکل 6-6) عملگرجهش روی نمايش درختی

 

نظريات

اين نظريات اغلب، نتايج مطالعات تجربي و آزمايش روي الگوريـتمهای ژنتيک مي باشند كه اغلب آنها روي كدگذاري باينري انجام گرفته اند.

ميزان سرعت عملگر برش- سرعت اين عمل عموما بالاست و در حدود %80 تا %95 مي باشد. هرچند براي برخي مسائل، سرعت درحدود %60 بهترين سرعت است.

ميزان سرعت عملگر جهش- در طرف ديگر سرعت عمل جهش بسيار كم مي باشد. بهترين نرخ سرعتهاي گزارش شده در حدود %5/0 تا %1 هستند.

سايز جمعيت ژنتيكي – ممكن است تعجب آور باشد كه بسيار بزرگ بودن اندازه جمعيت كارآيي  GA  را بهتر نمي كند. يعني سرعت يافتن راه حل زيادتر نمي‏شود. اندازه بهينه جمعيت ژنتيكي در حدود 20 تا 30 مي باشد. هر چند برخي اوقات سايزهاي 50 تا 100 نيز بعنوان يك سايز خوب گزارش شده اند. بهترين سايز جمعيت

بستگي به نوع رمزگذاري دارد. به اين معني كه اگر شما كروموزومي با 32 بيت داشته باشيد، اندازه جمعيت بايد بزرگتر از زماني باشد كه كروموزوم شما 16 بيتي است.

از روشهاي انتخاب، روش چرخ رولت  اساساً قابل استفاده مي باشد، اما بعضي اوقات روش  Rank مي تواند بهتر باشد. نوع رمزگذاري و عملگرهاي برش و جهش وابسته به مسأله و همچنين سايز مسأله هستند. در اينجا برخي كاربردهاي الگوريتم ژنتيك را بيان مي كنيم:

الگوريتمهاي ژنتيك براي حل مسائل مشكل مانند مسائل با پيچيدگي  NP استفاده ميشوند. همچنين براي ايجاد برنامه هاي ساده، هنرها، ايجاد تصاوير و موزيك بكار رفته اند. مزيت الگوريتمهاي ژنتيك در مشابهت و همساني آنهاست. همچنين پياده سازي و اجراي  GA  آسان است. شما فقط يكبار GA  را خواهيد داشت و مجبور به نوشتن كروموزوم جديد براي حل مسئله اي جديد نيستيد. يعني كافي است با رمزگذاري مشابهي تابع برازندگي را تغيير دهيد و اين كل كار است. در طرف ديگر انتخاب نوع رمزگذاري و تابع برازندگي مي تواند مشكل باشد. عيب  GA در زمان محاسباتي آن است يعني آنها نسبت به ديگر روشها كندتر هستند. اما با وجود كامپيوترهاي سريع امروزي اين مشكل، چندان بزرگ نيست. برخي ديگر از كاربردهاي الگوريتم ژنتيكي عبارتند از:

• سيستم هاي پوياي غيرخطي و تجزيه داده.
• طراحي شبكه هاي عصبي و نيز معماري.
• مسير و خط مسير روبات.
• ايجاد برنامه هاي  LISP ( برنامه نويسي ژنتيكي)
• طرح ريزي استراتژي.
• TSP و زمانبندي ترتيبي.
• يافت شكل و قالب مولكولهاي پروتئين.
• طرح توابعي براي ايجاد تصاوير.

 

در طول اين فصل با الگوريتمهاي ژنتيك، عملگرها و نحوه عملكرد آنها آشنا شديم.

 

زمانبندی انجام کارها با کمترین زمان تاخیر با استفاده الگوریتم ژنتیک :
در این الگوریتم ابتدا ترتیب های به صورت تصادفی به وجود می آیند سپس به احتمال 20 % به نسبت زمان اجرا ، سود کارها ، و مهلت کارها مرتب شده و وارد حلقه الگوریتم می شوند سپس با احتمال 80% عملگر الحاق روی کروموزوم ها انجام می شود در عملگر الحاق از روش دایره ای استفاده شده است بعد به احتمال 90% عمل جهش روی می دهد سپس ارزش فرزندان محاسبه شده بهترین فرزند هر نسل ذخیره می گردد در عمل الحاق والدینی که از لحاظ ارزش دارای ارزش بهتری هستند احتمال انتخابشان بالاتر است . سپس بعد از اجرای الگوریتم بعد از 1000 نسل بهترین فرزند بهترین فرزند ها جواب مسئله است این الگوریتم برای مسئله با ورودی 20 کار تا 95% موفقیت امیز است و جواب بهینه کامل را بدست می آورد.

الگوريتم کلونی مورچگان

Ant Colony Algorithm

مقدمه Ant Colony Algorithm:

هم اکنون کار روی سیستم های هوشمند با الهام از طبیعت از زمینه های خیلی پر طرف دار هوش مصنوعی است. الگوریتم های ژنتیکی که با استفاده از ایده تکامل داروینی و انتخاب طبیعی مطرح شده است, روش بسیار خوبی برای یافتن راه حل مسائل بهینه سازی است. ایده تکامل داروینی بیانگر این مطلب است که هر نسل نسبت به نسل قبل دارای تکامل است و آنچه در طبیعت رخ می دهد حاصل میلیون ها سال تکامل نسل به نسل موجوداتی مثل مورچه است.

الگوریتم کلونی مورچه برای اولین بار توسط دوریگو(Dorigo) و همکارانش به عنوان یک راه حل چند عامله (Multi Agent) برای مسائل مشکل مثل فروشنده دوره گرد(TSP) ارائه شده است(Traveling Sales Person).

 

2-2 بهينه سازي مسائل بروش کلوني مورچه(ACO) :

همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد(TSP). در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئله از مرتبه (n-1)! است که براي فقط 21 شهر زمان واقعا زيادي مي برد:

روز1013*7/1 =  S1016*433/2 = ms10*1018*433/2 = !20

با انجام يک الگوريتم برنامه سازي پويا براي اين مسئله ، زمان از مرتبه نمايي بدست مي آيد که آن هم مناسب نيست. البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ کدام کارايي مناسبي ندارند. ACO الگوريتم کامل و مناسبي براي حل مسئله TSP است.

 

2-2-2 مورچه ها چگونه مي توانند کوتاهترين مسير را پيدا کنند؟

مورچه ها هنگام راه رفتن از خود ردي از ماده شيميايي فرومون(Pheromone) بجاي مي گذارند البته اين ماده بزودي تبخير مي شد ولي در کوتاه مدت بعنوان رد مورچه بر سطح زمين باقي مي ماند. يک رفتار پايه اي ساده در مورچه هاي وجود دارد :

 

آنها هنگام انتخاب بين دو مسير بصورت احتمالاتي(Statistical)  مسيري را انتخاب مي کنند که فرومون بيشتري داشته باشد يا بعبارت ديگر مورچه هاي بيشتري قبلا از آن عبور کرده باشند. حال دقت کنيد که همين يک تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد :

همانطور که در شکل 1-1 مي بينيم مورچه هاي روي مسير AB در حرکت اند (در دو جهت مخالف) اگر در مسير مورچه ها مانعي قرار ديهم(شکل 2-1) مورچه ها دو راه براي انتخاب کردن دارند. اولين مورچه ازA  مي آيد و بهC  مي رسد، در مسير هيچ فروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد و بطور تصادفي و احتمالاتي مسير CED را انتخاب مي کند. اولين مورچه اي که مورچه اول را دنبال مي کند زودتر از مورچه اولي که از مسير CFD رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا)  انتخاب مي کنند. در نهايت مسير CED بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرومون بيشتري در آن وجود دارد.

نکه بسيار با اهميت اين است که هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اين کماکان احتمال است و قطعيت نيست. يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت که همه مورچه ها از مسيرCED  عبور خواهند کرد بلکه تنها مي توان گفت که مثلا 90% مورچه ها از مسير کوتاهتر عبور خواهند کرد. اگر فرض کنيم که بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچه فقط و فقط مسير پرفرومون تر را انتخاب ميکرد آنگاه اساسا اين روش ممکن نبود به جواب برسد. اگر تصادفا اولين مورچه مسيرCFD(مسير دورتر) را انتخاب مي کرد و ردي از فرومون بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.

نکته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير  AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند.

1-1	2-1
3-1	4-1

 

 

مزيتهاي ACO

همانطور که گقته شد «تبخير شدن فرومون» و «احتمال-تصادف» به مورچه ها امکان پيدا کردن کوتاهترين مسير را مي دهند. اين دو ويژگي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يکي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره اي) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايي که مسئله حل  شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت کوتاهي مسير بهينه(کوتاهترين) را بيابند.

 

4-2 کاربردهاي ACO :

از کاربردهاي  ACO مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود :

*.        مسير يابي داخل شهري و بين شهري

*.       مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا

*.       مسير يابي شبکه هاي کامپيوتري

 

 

 

5-2 زمانبندی انجام کارها با کمترین زمان تاخیر با استفاده از الگوریتم کلونی مورچگان :

در اینجا مسئله را با الگوریتم کلونی می خواهیم حل کنیم ابتدا 100 عدد مورچه مصنوعی تولید کرده وروی گراف ایجاد شده رها می کنیم نحوه محاسبه سود عاید شده به صورتی است که به نسبت زمان انتخاب کار سود بدست آمده تغییر  می کند بعد از اینکه مورچه ها یک مسیر را به تصادف پیمودند حال بهترین مورچه منظور مورچه که به نسبت بقیه مسیر بهتری را پیموده انتخاب شده و فرمون روی مسیر او پخش می شود برای مورچه برای انتخاب کار بعدی یک فرمون روی آن گره به نسبت زمان فعلی تاثیر گذار است دیگر عدد تصادفی ایجاد شده در هر مرحله هم مقداری از فرمون کل گره های گراف کم می شود .

مسئله زمانبدی کارها با احتساب کمترین زمان تاخیر

1-3 تعریف مسئله :

مسئله به دین شرح است :

در یک سیستم کامپیوتری تعداد فراوانی کار یا همان پردازه وارد صف آماده می شوند که تمامی این کارها درای یک ارزش و یک مهلت برای اجرا هستند طبیعتا هر کار نیز دارای یک مدت زمان اجرا نیز می باشد هر کار که در مدت زمان معین یا تا آن لحظه که مهلت برای اجرا  دارد اجرا شود یک ارزش برای سیتم دارد و از آن لحظه که مهلت اجرای آن تمام شروع شد به ازای هر واحد زمانی که تاخیر کرده * ارزش کارش زیان می کند حال اگر 5 کار با مقادیر متفاوت به سیستم داده شود ( تمام کارها در  همان لحظه صفر آماده اجرا هستند ) سیستم شروع به اجرای این کارها کند به ازای بعضی از کارها با تاخیر مواجه می شود که همان بیان گر اجرا نشدن به موقع کار است جمع تمام این تاخیر ها را تاخیر کل سیستم به ازای ورودی مورد نظر گویند که هر چه این تاخیر کمتر شود ارزش کسب شده برای سیستم می تواند بیشتر شود .

برای مثال :

0 1 2 3 شماره کارها

1 2 3 4 مهلت کار ها

4 3 2 1ارزش کارها

1 1 1 1 مدت زمان اجرا

برای چهار کار بالا !4 حالت متفاوت وجود خواهد داشت به طوری که اگر ترتیب اجرای کار به صورت 1 2 0 3 باشد تاخیر به وجود آمده برابر است با 2 واحد زمانی اما اگر ترتیب اجرا به صورت 3 2 1 0 می بود تاخیر کل برابر صفر می شود که این بهینه ترین جواب مسئله است ولی آن طور که مشاهده می شود مسئله از نوع Np – Hard  است و روش معمولی آن از پیچیدگی فاکتوریل استفاده میکند پس برای مقادیر بالاتر از 100 غیر قابل قبول است از لحاظ زمانی برای همین از دو رویکرد تکاملی  برای شرح آن استفاده می شود .

 

ارائه یک الگوریتم ژنتیک برای مسئله زمان بندی کار ها :

در بخش اول الگوریتم ژنتیک به صورت کامل شرح داده شد در این قسمت فقط به انواع توابع آن و روش های اتخاذ شده اشاره می شود .

جمعیت اولیه : 201

تعداد نسل های ارتقاء داده شده : 1500

روش Crass Over : روش گردشی ، چرخشی

روش Mutation  : تعویض جای دو خانه از حافظه

روش آنتخاب : روش چرخ رولت

تابع ارزشیابی مورد استفاده : با توجه به تر تیب کار ایجاد شده برای هر کروموزم تاخیر محاسبه می شود کمترین تاخیر بهترین فرزند نسل بود

احتمال جهش : 0.6

احتمال الحاق :  0.8

نمودار بهبود کارایی برای یک نمونه ورودی با 10 کار

 

ارائه یک الگوریتم Ant Colony برای مسئله زمانبندی کارها :

الگوریتم کلونی مورچگان در فصل دوم به صورت کامل شرح داده شد در این جا فقط به نوع انتخاب روش های مورد استفاده می پردازیم :

ابتدا به صورت اولیه یک مقدار برای هر گره در نظر گرفته می شود سپس با توجه به مقدار فرمون اولیه احتمال ولیه نیز برای هر گره انتخاب می شود هدف از بیان گره شماره کارها را با احتساب زمان انتخاب به یک ماتریس 3 بعدی تبدیل شده است که بعد اول نشان دهنده کار انجام گرفته فعلی و بعد دوم کاری است می خواهد انجام شود و بعد  سوم زمان حال سیستم از ابتدای اجرای ترتیب کار های فعلی است چون انتخاب کار 2 بعد از کار 1 با توجه به شرایط زمانی می تواند نتایج کاملا متفاوتی را حاصل کند  پس مجبورا مولفه زمان را نیز باید دخالت داده شود.

هر مورچه مصنوعی به صورت تثادفی کار خود را از روی شماره یکی از کارها آغاز سپس با استفاده از یک روش تصادفی و به نسبت شانسی که هر کار در زمان فعلی به نسبت فرمونی که روی خود دارد انتخاب می شود بعد از این حالت با تابع ارزشیابی بهترین فرزند انتخاب می شود و مسیر حرکتی این فرزند با فرمون بیشتر احاطه می شود در هر مرحله از اجرای الگوریتم مسیر های با فرمون بیشتر چون دارای شانس انتخابی بیشتری هستند بیشتر انتخاب می شوند ودر نهایت مسیر حرکتی یگانه می شود .

در هر مرحله  از انجام الگوریتم کل فرمون های گراف ها با یک درصد خاصی کاهش می یابند که همان میزان تبخیر فرمون است .

نمودار زیر روند تکامل مورچه ها را در حین انجام الگوریتم نمایش می دهد.

پیوست 1:

کد های مر بوط به پیاده سازی پروژه با ژنتیک در زبا ن برنامه نویسی Visual C#.Net

using System;

using System.IO;

using System.Collections.Generic;

using System.Text;

 

namespace SMTWTP_WITH_GA

{

class Program

 

{

قسمت تعریف متغیر ها و آرایه های مورد نیاز

private static double  [] cromozomtemp;

private static int[,] problem_input;

private static int[,] cromozom;

private static int[,] childtemp;

private static int[,] bestchildtemp;

private static int[] fitnesstemp;

private static int[] result=new int [10];

private static int n = 0, sumf = 0, minf = 0;

static void Main(string[] args)

{

int t = 0;

string[] str;

Random rnd=new Random();

int[] temp;

FileStream fs = new FileStream(“input3.txt”, FileMode.Open, FileAccess.Read);

BinaryReader br = new BinaryReader(fs);

Stream sr = fs;

StreamReader input = new StreamReader(sr);

 

n = int.Parse(input.ReadLine());

do

{

 

cromozomtemp = new double[n];

fitnesstemp = new int[201];

cromozom = new int[201, n];

childtemp = new int[201, n];

problem_input = new int[n, 3];

temp = new int[n];

bestchildtemp = new int[10, n];

 

قسمت گرفتن داده های ورودی از فایل و ذخیره ی آن روی ارایه ها

str = input.ReadLine().Split(‘ ‘);

for (int i = 0; i < n; i++)

{

problem_input[i, 0] = int.Parse(str[i]);

}

 

str = input.ReadLine().Split(‘ ‘);

for (int i = 0; i < n; i++)

{

problem_input[i, 1] = int.Parse(str[i]);

}

 

str = input.ReadLine().Split(‘ ‘);

for (int i = 0; i < n; i++)

{

problem_input[i, 2] = int.Parse(str[i]);

}

شروع الگوریتم

for (int ii = 0; ii < 10; ii++)

{

 

 

for (int k = 0; k < 201; k++)

{

تولید نسل اولیه

 

for (int i = 0; i < n; i++)

{

cromozomtemp[i] = rnd.NextDouble();

temp[i] = i;

}

 

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

if (cromozomtemp[i] < cromozomtemp[j])

{

t = temp[i];

temp[i] = temp[j];

temp[j] = t;

}

}

}

for (int i = 0; i < n; i++)

{

cromozom[k, i] = temp[i];

//  Console.Write(temp[i] + ” “);

}

//Console.WriteLine();

Random rnd2 = new Random();

int prob1 = rnd.Next(100);

if (prob1 <= 20)

sort(k);

}

// Console.ReadLine();

قسمت تکراری الگوریتم تکرار به اندازه نسل

for (int j = 0; j < 5000; j++)

{

 

 

fitness();

t = bestchild();

 

 

for (int i = 0; i < 100; i++)

{

crossover(sumf, i);

}

 

mutation();

replacechid(t);

//print(t, j);

 

}

Console.Write(“\r=> “+(ii*10+10)+”%”);

int z = retfit(t);

result[ii] = z;

for (int km = 0; km < n; km++)

{

bestchildtemp[ii, km] = childtemp[0, km];

}

}

Console.WriteLine();

print();

n = int.Parse(input.ReadLine());

} while (n != 0);

 

Console.ReadLine();

}

//////////////////////////////////////////////////////////

// functions part

/// /////////////////////////////////////////////////////

تابع الحاق

public static void crossover(int t,int l)

{

int k = 0, index, m, j = 0, f = 0; ;

bool set=false ;

Random rnd = new Random();

int[] father = new int[n];

int[] mather = new int[n];

int[] t1 = new int[n];

for (int i = 0; i < n; i++)

t1[i] = -1;

index = 0;

 

 

 

 

m = rnd.Next(t);

do

{

if (index == 201) index–;

 

k += fitnesstemp[index];

if (k >= m)

break;

index++;

} while (true);

 

for (int i = 0; i < n; i++)

{

father[i] = cromozom[index, i];

}

index = 0;

k = 0;

m = rnd.Next(t);

do

{

if (index == 201) index–;

k += fitnesstemp[index];

if (k >= m)

break;

index++;

} while (true);

 

for (int i = 0; i < n; i++)

{

mather[i] = cromozom[index, i];

}

 

if (rnd.Next() <= 90)

{

f = rnd.Next(n);

int d = f;

for (int i = 0; i < n; i++)

{

m = father[f];

for (j = 0; j < n; j++)

{

 

if (mather[j] == m)

{

t1[i] = j;

break;

}

}

f = j;

if (f == d)

break;

 

}

}

 

 

for (int i = 0; i < n; i++)

{

set = false;

for (j = 0; j < n; j++)

{

if (i == t1[j])

{

set = true;

break;

}

}

if (set)

{

childtemp[l * 2 + 1, i] = father[i];

childtemp[l * 2 + 2, i] = mather[i];

}

else

{

childtemp[l * 2 + 2, i] = father[i];

childtemp[l * 2 + 1, i] = mather[i];

}

}

 

 

}

تابع جهش

public static void mutation()

{

int k = 0, l = 0, h = 0, t = 0,p=0;

Random rnd = new Random();

for (int i = 1; i <201; i++)

{

h = rnd.Next(100);

if (h <= 50)

{

h = rnd.Next(4);

for (int v = 0; v < h + 1; v++)

{

/*p = problem_input[childtemp[i, 0], 0];

for (int iii = 0; iii < n / 2; iii++)

{

if (p < problem_input[childtemp[i, iii], 0])

{

p = problem_input[childtemp[i, iii], 0];

k = iii;

}

}

p = problem_input[childtemp[i, n / 2], 0];

l = n / 2;

for (int iii = n / 2; iii < n; iii++)

{

if (p > problem_input[childtemp[i, iii], 0])

{

p = problem_input[childtemp[i, iii], 0];

l = iii;

}

}*/

k = rnd.Next(n);

l = rnd.Next(n);

 

t = childtemp[i, k];

childtemp[i, k] = childtemp[i, l];

childtemp[i, l] = t;

}

}

}

}

تابع یافتن بهترین فرزند نسل

public static int bestchild()

{

int k = 0, t = 0, l = 0;

k = fitnesstemp[0];

l = fitnesstemp[0];

sumf = 0;

for (int i = 1; i < 201; i++)

{

if (k > fitnesstemp[i])

{

k = fitnesstemp[i];

t = i;

}

if (l > fitnesstemp[i])

{

l = fitnesstemp[i];

}

 

}

/*minf = l;

for (int i = 0; i < 201; i++)

{

fitnesstemp[i] += -l+1;

}*/

 

for (int i = 0; i < 201; i++)

{

sumf += fitnesstemp[i];

}

return t;

}

تابع جایگذاری نسل جدید روی نسل قدیم

public static void replacechid(int t)

{

for (int i = 0; i < n; i++)

{

childtemp[0, i] = cromozom[t, i];

}

for (int i = 0; i < 201; i++)

{

for (int j = 0; j < n; j++)

{

cromozom[i, j] = childtemp[i, j];

}

}

}

تابع ارزشیابی

public static void fitness()

{

int k = 0;

int j = 0;

int t = 0;

int ftemp = 0;

/* for (int l = 0; l < 201; l++)

{

j = 0;

k = 0;

ftemp = 0;

do

{

if (problem_input[cromozom[l, j], 0] >= k)

{

ftemp += problem_input[cromozom[l, j], 1];

j++;

}

else

{

t = k – problem_input[cromozom[l, j], 0];

ftemp -= (t * problem_input[cromozom[l, j], 1]);

j++;

}

k += problem_input[cromozom[l, j-1], 2];

 

} while (j < n);

fitnesstemp[l] = ftemp;

}*/

for (int i = 0; i < 201; i++)

{

int kj = 0;

int m = 0;

 

 

for (int l = 0; l < n; l++)

{

// Console.Write(cromozom[i, l] + ” “);

if (problem_input[cromozom[i, l], 0] < m)

{

kj += m – problem_input[cromozom[i, l], 0];

m += problem_input[cromozom[i, l], 2];

}

else

m += problem_input[cromozom[i, l], 2];

 

}

fitnesstemp[i]=kj;

//Console.Write(“\n {0}\n”,kj);

 

}

}

تابع چاپ جواب

public static void print()

{

int k =result[0];

int iindex =0;

int m=0;

int kj = 0;

for (int mn = 0; mn < 10; mn++)

{

if (k<result[mn])

{

k = result[mn];

iindex = mn;

}

}

Console.ForegroundColor = ConsoleColor.Green;

Console.WriteLine(“\nNasle :” + 1000);

for (int i = 0; i < 10; i++)

{

kj = 0;

m = 0;

k = result[i];

 

for (int j = 0; j < n; j++)

{

Console.Write(bestchildtemp[i, j] + ” “);

if (problem_input[bestchildtemp[i, j], 0] < m)

{

kj += m – problem_input[bestchildtemp[i, j], 0];

m += problem_input[bestchildtemp[i, j], 2];

}

else

m += problem_input[bestchildtemp[i, j], 2];

 

}

Console.WriteLine();

Console.Write(kj+” |’S Takhir\n”+k+”|’$ Sod  \n”);

}

}

public static int retfit(int t)

{

//return fitnesstemp[t] + minf – 1;

return fitnesstemp[t];

}

public static void  sort(int ikc)

{

Random rnd = new Random();

int prob=rnd.Next(1,4);

if (prob == 1)

{ /// SORT BY MOHLAT

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

if (problem_input[cromozom[ikc, i], 0] < problem_input[cromozom[ikc, j], 0])

{

int tkc = cromozom[ikc, i];

cromozom[ikc, i] = cromozom[ikc, j];

cromozom[ikc, j] = tkc;

}

}

}

}

else if (prob == 2)

{///SORT BY ARZESH

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

if (problem_input[cromozom[ikc, i], 1] > problem_input[cromozom[ikc, j], 1])

{

int tkc = cromozom[ikc, i];

cromozom[ikc, i] = cromozom[ikc, j];

cromozom[ikc, j] = tkc;

}

}

}

}

 

else

{///SORT BY ZAMANE EJRA

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

if (problem_input[cromozom[ikc, i], 2] > problem_input[cromozom[ikc, j], 2])

{

int tkc = cromozom[ikc, i];

cromozom[ikc, i] = cromozom[ikc, j];

cromozom[ikc, j] = tkc;

}

}

}

}

}

 

}

}

 

پیوست 2:

کد های مربوط به پیاده سازی پروژه با استفاده از الگوریتم کلونی مورچگان زبا نبرنامه نویسی Visual C#.Net

 

using System;

using System.IO;

using System.Collections.Generic;

using System.Text;

 

namespace SMTWTP_WITH_ANTCOLONY

}

class Program

}//قسمت تعریف متغیر ها

private static int[,] problem_input;

private static float[,,] phermon;

private static float[,,] probility;

private static int[,] ant;

private static int[] anttemp;

private static int[] fitnesst;

private static int[] fitnessbestchildt;

private static int[,] bestchild;

private static int n;// tedad pardazeha

private static int time=1;// zamane hal

private static float alpha = 1.0f, beta = 1.0f, p = 1.0f, q = 1.0f,sum = 0.0f;

private static int k=20;//tedade morcheha

private static int kn = 0;//zaman kol ejra

static void Main(string[] args)

{

int t = 1000;//tedad tekrare algorithm

int di = 10;//t/di=100

string[] str;

Random rnd=new Random();

FileStream fs = new FileStream(“input2.txt”, FileMode.Open, FileAccess.Read);

BinaryReader br = new BinaryReader(fs);

Stream sr = fs;

StreamReader input = new StreamReader(sr);

n = int.Parse(input.ReadLine());

problem_input = new int[n, 3];

ant = new int[k, n];

anttemp = new int[n];

bestchild = new int[t, n];

fitnesst = new int[k];

fitnessbestchildt = new int[t];

str = input.ReadLine().Split(‘ ‘);

// قسمت بارگذاری ورودی در آرایه های مورد نظر

for (int i = 0; i < n; i++)

{

problem_input[i, 0] = int.Parse(str[i]);

}

str = input.ReadLine().Split(‘ ‘);

for (int i = 0; i < n; i++)

{

problem_input[i, 1] = int.Parse(str[i]);

}

str = input.ReadLine().Split(‘ ‘);

for (int i = 0; i < n; i++)

{

problem_input[i, 2] = int.Parse(str[i]);

}

 

for (int i = 0; i < n; i++)

{

kn += problem_input[i, 2];

}

 

phermon = new float[n, n, kn+1];

probility = new float[n, n, kn+1];

 

// begin algorithm

setpher();

 

for (int i = 0; i < t; i++)

{

setpro();

for (int j = 0; j < k; j++)

{

settemp();

time = 0;

int row = rnd.Next(0, n);

int counter=0;

bool set =true;

bool setsel = false;

anttemp[0] = row;

time += problem_input[row, 2];

for (int sh = 0; sh < n – 1; sh++)

{

setsel = false;

float chance = (float)rnd.NextDouble();

 

for (int ii = 0; ii < n; ii++)

{

if (chance <= probility[row, ii, time])

{

set = true;

row = ii;

counter++;

anttemp

= row;

 

time += problem_input[row, 2];

setsel = true;

for (int zz = 0; zz < n; zz++)

{

if (set)

{

for (int aa = 0; aa < n; aa++)

{

if (anttemp[zz] == anttemp[aa] && anttemp[aa] != -1 && aa != zz)

{

chance = (float)rnd.NextDouble();

ii = -1;

counter–;

time -= problem_input[row, 2];

row = anttemp

;

set = false;

setsel = false;

break;

}

}

}

else

break;

}

}

if (setsel)

break;

}

}

for (int lk = 0; lk < n; lk++)

{

ant[j, lk] = anttemp[lk];

}

}

Console.Clear();

Console.Write(” {0}% “,i/di );

fitness();

 

setbestchild(i);

setpherbest(i);

tabpher();

}

fitnessbestchild(t);

 

Console.Clear();

Console.Write(” 100% “);

 

for (int iik = t-10; iik < t; iik++)

{

Console.ForegroundColor = ConsoleColor.Green;

for (int iin = 0; iin < n; iin++)

{

Console.Write(” {0} “, bestchild[iik, iin]);

}

Console.ForegroundColor = ConsoleColor.Red;

// Console.WriteLine();

//  Console.WriteLine(“Fit = {0}”,fitnessbestchildt[iik]);

Console.WriteLine();

int m = 0;

int kj = 0;

 

for (int j = 0; j < n; j++)

{

//Console.Write(bestchild[iik, j] + ” “);

if (problem_input[bestchild[iik, j], 0] < m)

{

kj += m – problem_input[bestchild[iik, j], 0];

m += problem_input[bestchild[iik, j], 2];

}

else

m += problem_input[bestchild[iik, j], 2];

 

}

Console.WriteLine();

Console.Write(kj + ” |’S Takhir\n” + fitnessbestchildt[iik]+ “|’$ Sod  \n”);

}

Console.ReadLine();

Console.ForegroundColor = ConsoleColor.White;

}

//تابع پخش فرمون اولیه

private static void setpher()

{

for (int i = 0; i <n; i++)

{

for (int j = 0; j < n; j++)

{

anttemp[j] = 0;

ant[i, j] = 0;

for (int l = 1; l <= kn; l++)

{

if (i == j)

phermon[i, j, l] = 0.0f;

else

phermon[i, j, l] = 0.01f;

}

}

 

}

 

}

 

تابع جمع احتمالات کلیه گره ها//

private static void takesum(int indexi,int indexl)

{

sum = 0;

for (int pp = 0; pp < n; pp++)

{

float temp = (float)(Math.Pow(phermon[indexi, pp, indexl], alpha) * (Math.Pow((float)problem_input[pp, 0] /indexl, beta)));

sum += temp;

}

}

تابع ست کردن احتمال هر گره

private static void setpro()

{

 

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

sum = 0.0f;

for (int l = 1; l <= kn; l++)

{

if (i != j)

{

takesum(i, l);

probility[i, j, l] = (float)((Math.Pow(phermon[i, j, l], alpha) * (Math.Pow((float)problem_input[j, 0] / l, beta)))) / sum;

}

else

probility[i, j, l] = 0.0f;

}

}

}

float kk = 0;

for (int i = 0; i < n; i++)

{

kk += probility[1, i, 0];

}

 

for (int i = 0; i < n; i++)

{

for (int l = 0; l < kn; l++)

{

for (int j = 1; j < n; j++)

{

probility[i, j, l] += probility[i, j-1, l];

}

}

}

 

}

تابع برگرداندن مقادیر اولیه به آرایه

private static void settemp()

{

for (int i = 0; i < n; i++)

{

anttemp[i] = -1;

}

}

 

 

تابع ارزش یابی

public static void fitness()

{

 

int kt = 0;

int j = 0;

int t1 = 0;

int ftemp = 0;

for (int l = 0; l < k; l++)

{

j = 0;

kt = 0;

ftemp = 0;

do

{

if (problem_input[ant[l, j], 0] >= kt)

{

ftemp += problem_input[ant[l, j], 1];

j++;

}

else

{

t1 = kt – problem_input[ant[l, j], 0];

ftemp -= (t1 * problem_input[ant[l, j], 1]);

j++;

}

kt += problem_input[ant[l, j – 1], 2];

 

} while (j < n);

fitnesst[l] = ftemp;

}

}

تابع یافتن بهترین فرزند نسل

public static void setbestchild(int kj)

{

int iindex=0;

int max = fitnesst[0];

for (int i = 1; i < k; i++)

{

if (max<fitnesst[i])

{

iindex = i;

max = fitnesst[i];

}

}

for (int i = 0; i < n; i++)

{

bestchild[kj, i] = ant[iindex, i];

}

}

تابع ست کردن فرمون به ازای بهترین فرزند

public static void setpherbest(int kj)

{

int kh = 0;

int po=0;

int to = 0;

int iin=0;

po = bestchild[kj,iin];

do

{

iin++;

to = bestchild[kj, iin];

kh += problem_input[to, 2];

phermon[po, to, kh] += 0.07f;

po = to;

} while (iin < n-1);

 

 

for (int i = 0; i < k; i++)

{

po = ant[i, iin];

iin = 0; kh = 0; to = 0;

 

do

{

iin++;

to = ant[i, iin];

kh += problem_input[to, 2];

phermon[po, to, kh] += 0.02f;

po = to;

} while (iin < n – 1);

}

}

 

تابع محاسبه ارزش بهترین فرزند

public static void fitnessbestchild(int kp)

{

 

int kt = 0;

int j = 0;

int t1 = 0;

int ftemp = 0;

for (int l = 0; l < kp; l++)

{

j = 0;

kt = 0;

ftemp = 0;

do

{

if (problem_input[bestchild[l, j], 0] >= kt)

{

ftemp += problem_input[bestchild[l, j], 1];

j++;

}

else

{

t1 = kt – problem_input[bestchild[l, j], 0];

ftemp -= (t1 * problem_input[bestchild[l, j], 1]);

j++;

}

kt += problem_input[bestchild[l, j – 1], 2];

 

} while (j < n);

fitnessbestchildt[l] = ftemp;

}

}

 

تابع تبخیر فرمون

private static void tabpher()

{

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

for (int l = 1; l <= kn; l++)

{

if (i == j)

phermon[i, j, l] = 0.0f;

else

if (phermon[i, j, l] > 0.02)

{

phermon[i, j, l] -= 0.01f;

}

}

}

 

}

 

}

}

}

 

منابع :

• Dorigo ,M., & Gambardella, L. M (1997) Ant colonies for the traveling salesman problem. BioSystems, 43 ,73-81
• Jearakul, C.,1999 2D and 3D Watefall Chart Control, [Online], Available: http:/www.codeguru.com.controls/Waterfall.shtml [Accessed 3/9/2003]
• Rule,K..1999 Flicker Free Drawing in MFC, [Online], Available: http:/www.codeproject.com/gdi/flickerfree.asp [Accessed 24/9/2003]
• http://en.wikipedia.org/wiki/Genetic_algorithm
• Goldberg, David E (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA.
• R. Garey and D. S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company.
• E. Goldberg (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley.

 

• Obitko (1998). Introduction to genetic algorithms, University of Applied Sciences, Czech technical university of parague.

 

• R. Vemuri (1997). Genetic algorithms, Computer Society meeting, Department of Applied Science University of California, Davis Livermore, CA, Ottawa.

 

• A. Dejong and W. M. Spears (1989). Using genetic algorithms to solve NP-complete problems, Proc. of the Third Int. Conf. on Genetic Algorithms.

[1] Genetic programming

[2] Crossover

[3] Mutation

[4] Fitness