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

بخشی از مقاله

کاربرد الگوریتم ژنتیک درموازنه زمان- هزینه پروژهها

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

واژههاي کلیدي

موازنه، هزینه، زمان، کنترل پروژه، الگوریتم ژنتیک.

1. مقدمه:

محققان از ابزارها و روش هاي مختلفی براي فائق آمدن بر مشکلات پیچیده دنیاي امروز استفاده می کنند. با پیشرفت و بهبود روش هـاي سنتی، روش هاي پیشین مانند برنامه ریزي خطی، غیر خطی و پویا جاي خود را به تکنیک هاي انعطاف پذیر تر مـی دهنـد. در ایـن میـان الگوریتم هاي تکاملی مخصوصاًو الگوریتم ژنتیک در بسیاري از موارد به خوبی عمل کرده اند. ایجـاد طـرح هـاي مناسـب بـراي مـدیریت وکنترل امور، در زمینه هاي مختلف از اهمیت ویژه اي برخوردار است. این می تواند همه زمینه هاي تولیدي و خدمات یا انجام پـروژه هـاي عظیم ملی و سایر زمینه ها را شامل شود.الگوریتم هاي تکاملی به طور اساسی با روش هاي جستجو و بهینه سازي سنتی فرق دارند. مهمترین تفاوت هاي بـین ایـن روش و سـایر روش هاي سنتی را می توان اینگونه بیان کرد:
الف. الگوریتم هاي تکاملی جمعیتی از نقاط را بطور موازي جستجو می کنند و به یک نقطه تنها نمی پردازند. ب. الگوریتم هاي تکاملی نیاز به اطلاعات اقتباسی و دانش کمکی ندارند. تنها تابع هدف و سطح برازندگی بر جهت گیري جستجو تـاثیر مـی گـذارد. ج. الگـوریتم هـاي تکاملی از قوانین انتقال احتمالی استفاده می کنند و نه از قوانین قطعـی. د. الگـوریتم هـاي تکـاملی بـراي اسـتفاده،کـاملاً سـاده و روشـن می باشند. الگوریتم هاي تکاملی می توانند جواب هاي بالقوه براي مساله داده شده را بیابند، اما انتخاب نهایی بـا کـاربر اسـت. بنـابراین در زمانی که جواب هاي چندي براي مساله وجود دارد، این الگوریتم ها به طور هم زمان چندین جـواب را شناسـایی مـی کننـد.[1] الگـوریتم ژنتیک یک نوع الگوریتم جستجو می باشد که بر اساس تکامل طبیعی موجودات پایه ریـزي شـده اسـت. ایـن الگـوریتم از مکـانیزم بقـاي مناسب ترین رشته ها استفاده کرده و با انجام عملگرهاي مناسب بر روي رشته ها به طریقی هوشمندانه بهترین جواب ها را حفظ می کنـد.در این تحقیق سعی براین است تا کاربردهاي این الگوریتم را در موازنه زمان- هزینه پروژه ها مورد بررسی قرار داده و الگوریتم مناسـب بـا معیارهاي انتخاب شده در یک مورد خاص، توسعه و بهبود داده شود.
الگوریتم ژنتیک علاوه بر استفاده در یافتن نقـاط بهینـه توابـع، در مـسائل مختلفـی از قبیـل طراحـی کنتـرل کننـده هـا، بهـره بـرداري از سیستم هاي قدرت، یادگیري ماشین، پردازش تصاویر، تعیین هویت سیستم، تقسیم بندي سیستم هـا، تعلـیم شـبکه هـاي عـصبی و بهینـه نمودن سیستم هاي عصبی – فازي [ 2] تا حتی تقسیم بندي انواع سرطان ها[3]، کارایی خود را نشان داده اند.برخی از این تلاش ها در مورد پیشبرد الگوریتم هاي تکاملی براساس تکنیک هایی براي فرزندان بهتر، مانند استفاده از عملگرهاي تکـاملی جدید8]،7،6،[4 5، تغییر ارائـه مـساله در طـول، حـل مـساله12]،11،[9 10، تنظـیم پویـایی و تطـابق پارامترهـاي الگـوریتم هـاي تکاملی،[6 13] و ترکیب با دیگر تکنیک هاي بهینه سازي 17]،16،15،[14 می باشد.

2. موازنه زمان – هزینه پروژه ها:

به طور کلی در فرایندهاي کنترل پروژه، سه موضوع متفاوت ظهور می یابد:

موازنه زمان هزینه
تخصیص منابع
تسطیح منابع
موازنه شامل مینیمم کردن هزینه پروژه می باشد، بطوریکه پروژه بتواند در زمان مطلوب به پایان برسد. تخصیص منابع شامل مینیمم کردن زمان پروژه است بدون تخطی از محدودیت هاي منابع پروژه و تسطیح منـابع شـامل مینـیمم کـردن مقـدار مـاکزیمم اسـتفاده از منـابع و همچنین نوسانات دوره به دوره در تخصیص منبع می باشد، بطوریکه زمان مطلوب پروژه حفظ شود.[18]اکثر پروژه هاي بزرگ مخصوصاًو پروژه هاي ساخت و ساز، از شبکه اي وسیع از فعالیت ها ساخته می شوند و هر فعالیتمعمولاً می تواند، در زمان هاي متفاوتی به انجام برسد. . اگر فعالیتی در زمانی معمولی یا نرمال انجام پذیرد، داراي هزینه اي نرمـال مـی باشـد کـه معمـولاًحداقل هزینه یک فعالیت می باشد و اگر زمان فعالیت را فشرده کنیم، بر هزینه آن افزوده می شودمعمولاً. زمانی بین این دو نهایـت بـراي اجراي پروژه مناسب می باشد. در سطحی بالاتر، چون پروژه نیز شبکه اي از فعالیت ها است، بنابراین می تواند در زمانهاي مختلفـی انجـام پذیرد. اینکه یک پروژه کی و چه زمانی انجام پذیرد، موضوع اصلی در موازنه زمان – هزینه پروژه هـا مـی باشـد. بنـابراین بایـد ترکیبـات مختلف فعالیت ها شکل گرفته و بهترین آنها انتخاب شود. نکته جالب اینجاست که مقدار این ترکیبات گاهی به حـدي زیـاد مـی شـود کـه بکارگیري روش هایی مانند برنامه ریزي ریاضی یا روش هاي ابتکاري غیر ممکن می نماید.همچنین، پیشرفت هاي تحقیقی مهمی در زمینه بهینه سازي استفاده از منابع در ساخت و ساز انجام شده است که با استفاده از روش هـاي متعددي مانند برنامه ریزي خطی، برنامه ریزي اعداد صحیح، برنامه ریزي پویا و الگوریتم ژنتیک توسعه یافته انـد. ایـن مـدلها را مـی تـوان مطابق با اهداف بهینه سازیشان به چند دسته تقسیم بندي کرد:

- مینیمم کردن زمان پروژه و / یا بهبود استفاده از منابع.
- مینیمم کردن زمان و هزینه براي ساخت و ساز هاي غیر تکراري با استفاده از تحلیل موازنه زمان – هزینه.
- مینیمم کردن زمان و / یا هزینه براي ساخت و سازهاي تکراري.[19]

3. انواع تکنیک هاي بکارگرفته شده در موازنه زمان – هزینه پروژه:

در موازنه زمان هزینه حالت هاي مختلفی ممکن است پیش آید، بر پایه اختیارات مدیر پروژه، بودجه در نظر گرفته شده و زمان مورد انتظـار براي انجام پروژه. به طور کلی همه این حالات را می توان در سه دسته تقسیم بندي کرد:

الف: براي تغییرات عوامل هزینه و زمان محدودیتی وجود ندارد:
ب: تاریخ تکمیل مشخص شده:
ج: بودجه معینی براي تکمیل پروژه تعیین شده است .[18]

موازنه زمان - هزینه پروژه ها داراي تاریخچه اي طولانی می باشد و بدین منظور از ابزارها و تکنیک هاي زیادي مانند برنامه ریزي خطـی و غیر خطی، الگوریتم هاي ترکیبی، الگوریتم هاي ابتکاري و الگوریتم ژنتیک استفاده شده است. در حالیکه استفاده از برنامه ریزي خطـی و غیر خطی داراي سابقه طولانی تري می باشند، استفاده از الگوریتم ژنتیک به یک دهه اخیر برمی گردد. در ادامه ما ضمن بیان مختصري از همه روش هاي بکار گرفته شده در موازنه زمان – هزینه پروژه ها ، الگوریتم هاي ژنتیک بکار گرفته شده را به تفصیل شرح می دهیم.

4-ک مدل هاي برنامه ریزي ریاضی:

بر پایه سه نوع مدلی که در بالا مطرح شد، مدل هاي برنامه ریزي ریاضی موثري توسعه یافته اند. اما این روش ها داراي نقـاط ضـعفی نیـز می باشند. از بارزترین ضعف هاي برنامه ریزي ریاضی این است که در مبحث فوق درحالیکه محاسبات ریاضی فراوانی براي مسائل پیچیـده موازنه به کمک روش هاي برنامه ریزي ریاضی لازم است، در برخی موارد شرایطی براي توابع هدف چندگانه پیش می آید کـه هـیچ روش برنامه ریزي خطی نمی تواند جواب بهینه را بیابد و ناچار به استفاده از سایر روش ها هستیم . براي مثال در[20] مساله اي از کنترل بهینـه

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

3-2 روش هاي هیوریستیک:

اکثر الگوریتم هاي ابتکاري با فرض خطی بودن رابطه هزینه و زمان برنامه ریزي شده است، که غیر واقعی می باشد. همچنـین روش هـاي هیوریستیک بر پایه قوانین سرانگشتی قرار دارند. آنها جواب هاي خوبی ایجاد می کنند، ولی رسیدن به جواب بهینه را تـضمین نمـی کننـد، درحالیکه رابطه زمان – هزینه را بصورت خطی در نظر می گیرند. علاوه بر این اغلب جواب هاي حاصله از این روش هـا بـازه اي را بـراي جواب بهینه در نظر می گیرند و این مساله را براي تحلیل سناریو هاي مختلف (اگر – آنگاه ) مشکل می ،کنـد.[21 23] بنـابراین نیـاز بـه توسعه الگوریتم هایی که بتوانند جواب هاي نزدیک به بهینه و مناسب را با روابـط هزینـه – زمـان غیـر پیوسـته ایجـاد کننـد، وجـود دارد.

مهمترین الگوریتم ارائه شده در این رابطه بوسیله زیمنس ارائه شده است. کاربرد اصلی این الگوریتم، براي حل مسائل مربوط بـه مـدل دوم مسائل موازنه زمان- هزینه می باشد.

3-3 الگوریتم هاي ژنتیک:

الگوریتم ژنتیک، روش جستجویی الهام گرفته از تکامل طبیعی موجودات است. ایـن روش بوسـیله جـان هلنـد4 و همکـارانش در دانـشگاه میشیگان ارائه شد و بوسیله گلدبرگ توسعه داده شـده و شناسـانده شـد و بـه سـرعت در بـسیاري از شـاخه هـاي علـوم گـسترش یافـت.

الگوریتم هاي ژنتیک برپایه عناصر ژنتیکی می باشند. آنها از تئوري هاي تکامل زیستی براي حل مسائل بهینه سـازي اسـتفاده مـی کننـد.الگوریتم ژنتیک اولیه جواب هاي نامزد (اعضاء) را به عنوان رشته اي از ژن ها که کروموزوم نامیده می شوند، در نظر می گیرد. بـراي مثـال اگر جواب ها شامل اعداد باشند، ژن ها می توانند بوسیله بیت ها و کروموزوم ها نیز بوسیله نمایش باینري اعداد درنظر گرفته شوند.
جمعیت الگوریتم ژنتیک از جواب هاي نامزد بوسیله اجراي عملگرهاي ایجاد شده بوسیله تغییرات ژنتیکی طبیعی ایجاد می شود.چند عملگر عمده در تمام الگوریتم هاي ژنتیک وجود دارد:
- ایجاد مجموعه اي از اعضاء
- ارزیابی اعضاء
- انتخاب
- تقاطع
- جهش
حلقه الگوریتم ژنتیک ادامه می یابد تا اینکه یک جواب بهینه( یا مناسب) براي مساله یافت شود.
نخستین کاربردهاي الگوریتم ژنتیک در موازنه به کارهاي فنگ5 و همکارانش بر می گردد. در این الگوریتم، کروموزوم ها بصورت رشته اي از ژن ها، که در حقیقت، مدهاي اجرایی فعالیت ها می باشند، در نظر گرفته شده است. این الگوریتم، با انتخاب دو رشته از فعالیت ها، که در یکی، همه فعالیت ها، مدي را که بیشترین زمان، و در دیگري کمترین زمان، را شامل می شود، شـروع مـی شـود و N-2 رشـته دیگـر بـه صورت تصادفی انتخاب می شود. سپس منحنی موازنه و پوسته محدب، که یک مرز محدب می باشد که از پـایین همـه جمعیـت را شـامل می شود، ایجاد می شود. این منحنی ها با مکانیزمی به سمت محورها حرکت داده میشوند و زمانی که پس از چند تکـرار، ایـن منحنـی هـا ثابت ماندند، منحنی شامل جواب هاي بهینه می باشد.[21] البته این الگوریتم فعالیت ها را در حالتی که روابط بین آنها روابط پایان- آغـاز
(FS) می باشد، در نظر می گیرد و براي پشتیبانی از سایر حالات نیز باید تغییراتی در آن صورت گیرد، همچنین ایـن الگـوریتم محـدودیت هاي منابع را نیز در نظر نمی گیرد. الگوریتم مذکور به موازنه همزمان هزینه و زمان پروؤه ها می پردازد و هردو را بطور همزمان کاهش می دهد، اما منحنی موازنه زمان- هزینه در این الگوریتم ممکن است مجموعه جواب هاي بهینه واقعی را به طور صحیحی نشان ندهد.پس از آن لی و لو6 الگوریتمی ارائه دادند که مشکلات الگوریتم هاي سنتی را برطرف می نمود.[24] بدین گونه که بر اثر جهش یا تقـاطع ممکن بود که برخی از جواب ها نشدنی شوند، بدین دلیل که جمع کل کاهش هاي صورت گرفته بر روي یک رشته، از مقـدار ثابـت تعیـین شده بوسیله کاربر به منظور کاهش، بیشتر یا کمتر شود و این الگوریتم براي فائق آمدن بر این مشکل طراحی شد. اگـر چـه ایـن الگـوریتم، رویه هاي الگوریتم هاي سابق را بهبود می داد، اما خود نیز داراي نقاط ضعفی بود. در مسائل دنیاي واقعی موازنه زمـان- هزینـه بـا تغییـر زمان در یک فعالیت، ممکن است مسیر بحرانی دچار تغییر شود و مسیرهاي بحرانی متفاوتی بوجود آیند، همچنین باید چـک شـود کـه آیـا می توان این فعالیت را فشرده کرد یا نه؟ از دیگرنقاط ضعف این الگوریتم این است که از متغیرهاي پیوسته استفاده می کند و این در دنیاي واقعی زیاد عملی نیست. بنابراین باید پس از اجراي الگوریتم، از مکانیزمی براي رند کردن اعداد استفاده شود. همچنین مانند الگوریتم هـاي ژنتیک پیشین، زمان رسیدن به جواب هاي بهینه نامعین است.الگوریتم دیگري بوسیله هگازي7 ارائه شده است، که به طور خلاصه به شکل زیر عمل می کند: در مدل پیشنهادي، هر فعالیـت در پـروژه می تواند به 5 روش مختلف انجام شود. هر روش ساخت ترکیبی از منابع، تجهیزات و مواد بعلاوه تکنولوژي ساخت اسـت. بـراي هـر روش ساخت قبل از تحلیل 3 عنصر داده موردنیاز است: اندیس آن، زمان ارزیابی شده براي فعالیت و هزینه فعالیت. مـدل بیـان شـده بـسیاري از محدودیت هاي سایر الگوریتم ها را ندارد و داراي چندین مشخصه ویژه می باشد:
.1 روابط هزینه – زمان بصورت گسسته درنظر گرفته می شود.

.2 اجرا به کمک یک نرم افزار قدرتمند انجام می شود.
.3 این الگوریتم با جستجوي بخش کوچکی از فضاي جواب به همگرایی می رسد.
.4 همچنین این الگوریتم موعد مقرري را براي اجراي پروژه و جریمه تاخیر و پاداش تسریع را درنظر می گیرد.[25]

مهمترین ضعف این الگوریتم طبیعت تصادفی آن است که نیاز به زمان پردازش زیادي براي شبکه هاي بزرگ دارد. به هرحال بـراي بهبـود برنامه ریزي می توان به روش هاي زیر متوسل شد: وابسته کردن الگوریتم به ارزیابی هزینه ها- تسطیح و تخصیص منابع- افزایش سرعت الگوریتم و درنظرگرفتن تاثیر فشرده سازي یک فعالیت بر سایر فعالیت ها. یک نقطه ضعف این الگوریتم این است که در آن تابع برازنـدگی تنها شامل یک پارامتر هزینه است و شامل زمان نمی شود، یعنی بجاي استفاده از تابع هدف چندگانه، تابع هدفی واحد دارد و پـارامتر زمـان به عنوان مقداري ثابت بوسیله کابر وارد می شود.

الگوریتم ژنتیک دیگري توسط زنگ8 و همکارانش در [26] ارائه شده است که از رویکرد وزن تطبیقی اسـتفاده مـی کنـد. ایـن الگـوریتم براي مسائل نوع اول موازنه طراحی شده است، یعنی حالتی که در آن، براي تغییرات عوامل هزینه و زمان، محدودیتی وجود ندارد.

4. توسعه الگوریتمی جدید براي موازنه زمان- هزینه:

ص-ک انتخاب روش کدگذاري مناسب براي مساله:

مشکل کدگذاري در مرور ادبیات الگوریتم ژنتیک مشاهده می شود. مسائلکاملاً متفاوت، نیازمند کدگذاري ژنتیکـیکـاملاً متفـاوتی بـراي ایجاد جواب هاي خوب می باشند. همراه با ادامه یافتن تحقیقات در زمینه الگوریتم ژنتیک مساله صحت کدگـذاري نیـز از اهمیـت خاصـی برخوردار است. کدگذاري صحیح براي مسائلی که براي آنها کد ها طراحی می شوند، بسیار موثر است. کدگذاري صحیح قابل تغییر و توسعه جهت حل انواع مختلف مسائل می باشد.اعداد صحیح و حقیقی می توانند به عنوان رشته هاي بیتی به روش ها ي مختلف نشان داده شـوند. مقـادیر واقعـی مـی تواننـد بـه مقـادیر صحیح و مقادیر صحیح نیز می توانند با استفاده از نمایش باینري استاندارد نشان داده شوند. البتـه کدگـذاري هـاي اولیـه داراي مـشکلات زیادي نیز می باشند. کدگذاري باینري استاندارد داراي معایب عدیده اي می باشد. براي مثـال اعـداد صـحیح 15 و 16 بـصورت 0111 و 1000 نشان داده می شوند، که از ارقامکاملاً متفاوتی تشکیل شده است .[27 ] استراتژي هـاي کدگـذاري دیگـري در الگـوریتم هـاي تکاملی مورد استفاده قرار گرفته اند. براي مثال می توان از درخت ها، کدگذاري ماتریسی و کدگذاري ناهمگن ساخت یافته نام بـرد. چـالش ها براي تحقیقات، تشخیص راه هایی است که این آرایش هاي کدگذاري براي حل مسائل از نوع ترکیبی، با یکدیگر یکپارچه شوند.[28]روش کدگذاري که براي این الگوریتم انتخاب می شود، مشابه با سایر الگوریتم هاي ژنتیـک در مـورد موازنـه مـی باشـد. در ایـن روش از کدگذاري حقیقی استفاده می شود. چون هر فعالیت می تواند به چندین روش ساخت انجام پـذیرد، لـذا مـا نمـی تـوانیم از روش کدگـذاري باینري براي رشته ها استفاده کنیمطبیعتاً. اگر هر فعالیت تنهـا مـی توانـست در دو مـد بـه انجـام پـذیرد، روش کدگـذاري بـاینري بـدلیل ویژگیهاي مطلوبش می توانست نتایج خوبی داشته باشد. لذا ما ترجیع می دهیم که از کدگذاري حقیقی استفاده کنیم. بدین شـکل کـه هـر رشته از کروموزوم ها حاوي مجموعه از فعالیت ها می باشد. در این روش، ما به هر فعالیت یک شماره منحصر بفرد می دهیم . ایـن شـماره همان شماره اي است که در نرم افزار MSP براي فعالیت ها بکار برده شده است. در حقیقت ترتیب این رشته ها براسـاس همـین شـماره انجام می شود. همچنین هر ژن حاوي مقداري است که این مقدار به روش ساخت فعالیت اشاره دارد. شکل (1)، نشان دهنـده ایـن نـوع از کدگذاري می باشد.

شکل 1. روش کدگذاري مناسب براي مساله

4-2 روش مناسب انتخاب:

الگوریتم هاي ژنتیک و استراتژي هاي تکاملی، دو نوع از الگوریتم می باشند که سعی در استفاده از مکـانیزم هـاي طبیعـی دارنـد. مکـانیزم انتخاب این الگوریتم ها نقشی مهم جهت هدایت جستجو به سمتی دارند که از یک طرف اعضاي بهتر انتخاب شوند، و از طرف دیگر تنـوع جمعیت حفظ شود.[29] در الگوریتم هاي اولیه، روش مورد استفاده براي تابع برازندگی، روش پیشنهادي بوسیله هلند بود، که عبـارت مـی باشد از نسبت برازندگی هر عضو به میانگین برازندگی همه اعضا ي جمعیت. در 1985 جیمز بیکر9 از رتبه رشته هـاي جمعیـت بـه جـاي نسبت برازندگی هر عضو به میانگین کلی خبر داد. نتایج کارهاي تقریباًاو موفقیت آمیز بودند. اما به نظر می رسید که این روش نمی توانـد باعث تحولی عظیم در الگوریتم هاي ژنتیک شود. دلایل زیادي براي آن وجود داشت. نخست اینکه بیکر از این روش جهت کاهش سرعت همگرایی استفاده کرد، که البته این تنها کار برد این روش نبود. دوم اینکه آزمایشات استاندارد مناسـبی روي آن انجـام نگرفـت. تـست هـا معمولاً ساده و کوچک بودند. به هر حال آزمایشات اخیر نشان می دهد که این روش حتی می تواند سرعت جستجو را بالا ببرد. بحث هـا وشواهد نشان می دهد که این روش از روش تکثیر متناسب با برازندگی، بهتر است.[30] از آنجا که این الگوریتم براي پروژه هاي با تعـداد نسبتاً زیادي فعالیت، توسعه یافته است، و روش انتخاب مسابقه اي نیز داراي قوت زیادي در ایجاد نسل هـاي جدیـد اسـت، روش برگزیـده شده براي عملگر انتخاب، انتخاب مسابقه اي بود. انتخاب مسابقه اي بدین شکل عمل می کند که تعداد t عضو از جمعیـت را انتخـاب مـی کنیم و بهترین آنها را در یک جمعیت میانی کپی می کنیم و این کار را تا N بار تکرار می کنیم. اغلب این تورها بین دو عضو انتخـاب مـی شوند، اما می توان اندازه گروه را به طور اختیاري، به مقداري که اندازه تور نامیده می شود، تعیین کرد.[31] شاید دو جنبه بسیار آشکار ایـن نوع انتخاب، سادگی اجرا و پتانسیل بالقوه آن براي موازي کاري باشد. در میان جمعیت داده شده، t عضو انتخاب شده و بهترین آنها بـراي مرحله تقاطع انتخاب می شوند و این کار تا رسیدن به حد مطلوب جمعیت میانی ادامه دارد .[ 32] افزایش فشار رقابتی مـی توانـد بوسـیله اندازه تورها انجام شود، بطوریکه برنده تورهاي کوچک داراي برازندگی کمتري نسبت به برنده تورهاي بزرگ است.[33] البته، همچنان که در بخش تحلیل به طور مفصل بحث شده است، این عملگر با عملگر برشی، جایگزین شد.
از میان سایر روش هاي انتخاب، انتخاب برشی روشی مناسب می باشد، و براي جمعیت هاي زیاد، مناسب ترمی باشد. همچنین مـی تـوان پارامتر برش را دلخواه تنظیم کرد. در انتخاب اندازه مطلوب، باید به چندین نکته دقت کرد: نخست اینکه اگـر ایـن مقـدار را بـزرگ در نظـر بگیریم احتمال توقف در بهینه هاي محلی افزایش می یابد که این بدین دلیل است که با افزایش بیش از حد اندازه برش تنوع جمعیتی کم می شود. به طور خلاصه این بدان معنی است که، ما بر چند کروموزوم خوب اصرار می ورزیم درحالیکه ممکن است بهتر از آنهـا نیـز وجـود داشته باشد. هرچند که با این کار سرعت رسیدن به بهینه را افزایش می دهیم. عاقلانه است که میان این دو موضوع، یک توازن بوجود آید.

4-3 انتخاب روش تقاطع مناسب براي مساله:

هلند بیان کرد که یک ابتکار خوب این است که، نمونه هایی جدید از اسکیماهایی ایجاد کنیم که برازندگی مـشاهده شـده آنهـا از میـانگین برازندگی کل جمعیت بیشتر است و این نمونه ها از اسکیما ها محتمل تر است که عملکرد بالاتري داشـته باشـند. هلنـد یکـی از نخـستین تحلیل ها را در مورد عملگر ترکیب مجدد که ترکیب مجدد یک نقطه اي نامیده می شد، را ارائه کردبعداً. دي یانـگ10 ایـن تحلیـل را بـه ترکیب مجدد n نقطه اي گسترش داد.[34]

برخی از متخصصان الگوریتم ژنتیک معتقدند که اگر فرایند تقاطع را از الگوریتم ژنتیک حذف کنیم، حاصل دیگر الگـوریتم ژنتیـک نیـست.البته چنین ادعایی در مورد عملگر جهش وجود ندارد. در حقیقت بسیاري معتقدند که آنچه باعث تمایز الگوریتم ژنتیک از سایر الگوریتم هاي بهینه سازي می شود، استفاده از عملگر تقاطع است.[35]
سیسوردا احتمال اختلال در اسکیما را براي تقاطع هاي یک نقطه اي، دو نقطه اي و یکنواخت مقایسه کرده است. جالب است که درحالیکـه تقاطع یکنواخت تا اندازه اي از تقاطع یک نقطه اي و دو نقطه اي مخرب تر است، به طول اسکیما ارتباطی ندارد. همچنین سیـسوردا نـشان داد که طبیعت بسیار مخرب تقاطع یکنواخت می تواند به شکل دیگري نیز دیده شود: تقاطع یکنواخت بسیار مایل است کـه نمونـه هـایی از اسکیماهاي جدید و مناسب تر را از اسکیماي با کیفیت پایین نسبت به تقاطع هاي یک نقطه اي و دو نقطه اي ایجاد کند.
بر پایه مشاهدات بالا ما اجراي الگوریتم را در دو دسته تقسیم بندي می کنیم:
اگر تعداد فعالیت ها کمتر از 75 باشد.
اگر تعداد فعالیت ها بیشتر از 75 باشد.
حالت اول:

در حالت اول روش انتخابی براي تقاطع، استفاده از تقاطع دو نقطه اي است. از تحلیل هاي بالا میتوان نتیجه گرفت که این روش تقاطع، در زمانی که طول کروموزوم ها زیاد نباشد، می تواند بسیار موثر باشدطبیعتاً. استفاده از سایر روش ها مثل تقاطع یکنواخت و یا چنـد نقطـه اي نمی تواند جالب باشد. درحالیکه مسائل حالت اول داراي تعداد متوسطی از فعالیت است، یا داراي تعدادنسبتاً کمی از فعالیت است، استفاده از روش تقاطعی با مقدار متوسط کارایی می تواند موثر باشد.

حالت دوم:
در آخرین حالت روش پیشنهادي براي تقاطع استفاده از تقاطع یکنواخت است.
اجراي تقاطع یکنواخت،کاملاً مجزا از سایر تکنیک هاي تقاطع است. تقاطع یکنواخت، نخست نیاز به ماسک11 هاي تقـاطع تـصادفی دارد.
ژن هاي فرزندان مطابق با این ماسک ایجاد می شوند. در جاهایی که مقدار ژن ماسک برابر با 1 است، ژن مورد نظر از والد اول و درجـایی که مقدار آن برابر با صفر است از والد دوم انتخاب می شود. فرزند دوم نیز با استفاده از مکمل این ماسک یا با اسـتفاده از ماسـک تـصادفی جدیدي ساخته می شود و این فرایند ادمه می یابد.[36] در[37] آزمایشی انجام شده است که نشان مـی دهـد کـه در میـان عملگرهـاي مختلف، عملگر تقاطع یکنواخت داراي بیشترین نرخ ترکیب رشته ها می باشد.

این تقاطع براي مسائل لارج اسکیل12 می تواند موثر باشدطبیعتاً. اگر یک کرومـوزوم داراي جایگـاهی خـاص باشـد، بـه هـم ریخـتن آن کروموزوم با کمک تقاطع یکنواخت می تواند یک جواب بسیار خوب را به یک جواب بسیار بد تبدیل کند، هر چند که برعکس آن نیز ممکن است. خلاصه این مطالب و بحث ها در شکل (2) نشان داده شده است:

شکل 2. انتخاب روش مناسب تقاطع در الگوریتم جدید

4-4 انتخاب روش جهش مناسب:

فوگل13 طرح می کند که ترکیب مجدد براي بیشتر سیستم هاي تکامل طبیعی ضعیف است. بدین دلیل که آنها به طور وسیع پلی تروفیـک(یک ژن می تواند چندین ویژگی را تحت تاثیر قرار دهد) و پلی ژنیک (یک خصوصیت ممکن است بوسیله چندین ژن تاثیر بپذیرد) هـستند.
پس این سیستم ها اجزایی با برازندگی بالا براي ترکیب مجدد جهت استفاده ندارد. فوگل بحـث مـی کنـد کـه جهـش بـراي ایـن نـوع از سیستم ها بهتر است.[36] در[38] مقایسه اي میان عملگرهاي تقاطع و جهش انجام شده است.احتمال اینکه متغیري دچار جهش شود، طوري تنظیم شده است که با تعداد متغیرها نسبت عکس داشته باشد. هرچه رشته اي داراي تعـداد بیشتري متغیر باشد، احتمال جهش در یک رشته کمتر می شود. مقالات متفاوتی نتایج نرخ جهش را ارائه کرده انـد. در برخـی اشـاره شـده است که نرخ جهش 1/n نتایج خوبی براي کلاس وسیعی از مسائل تستی ایجاد می کنـد.[1] بـه هرحـال نـرخ جهـش از انـدازه جمعیـت مستقل است. این الگوریتم به گونه اي طراحی شده است که در دو حالت بر حسب تعداد فرایندها جهش هایی متفاوت را انجام دهد. خلاصه این عملگر در شکل (15-3) آمده است.