[Zohreh Gholami]

جامع ترین مقاله درباره الگوریتم ژنتیک (Genetic Algorithm - GA)


چکیده
الگوریتم ژنتیک (Genetic Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکامل است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند.

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

کلاً این الگوریتم‌ها از بخش های زیر تشکیل می‌شوند: تابع برازش، نمایش، انتخاب، تغییر.


فهرست مطالب


الگوریتم ژنتیک، هیوریستیک، ترکیب و جهش، تکامل طبیعی داروین، معمای هشت وزیر، پیشگامان متا، meta4u.com

[Zohreh Gholami]

فصل اول:


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

انشاءالله مطالعۀ این فصل مفهومی ساده و روشن از موضوعِ این نوشتار را برای شما خوانندۀ محترم به تصویر خواهد کشید و شما را در درک آسان و سریع فصول بعدی یاری خواهد رساند.


1-2- به دنبال تکامل...
بسیاری از دانشمندان و اندیشمندان، میل به تکامل را مهترین عامل پیشرفت دستگاه آفرینش و انسان می‌دانند. از این دیدگاه هر پدیده‌ای را که بنگرید، یک مسأله جستجوست. انسان همواره می‌کوشد تا به تکامل برسد، از این رو می‌اندیشد، می‌پژوهد، می‌کاود، می‌سازد، می‌نگارد و همواره می‌کوشد تا باقی بماند. حتی می‌‌توان گفت که میل به زادن فرزند، گامی در برآوردن این نیاز و البته دیگر جانداران است. می‌توان این تلاش در راه رسیدن به تکامل را یک مسألۀ جستجو تعبیر کرد.

کوشش یک مؤسسه اقتصادی یا تولیدی –که تابعی برای تبدیل داده‌ها به ستادهاست- برای کمینه کردن هزینه‌ها و بیشینه کردن سود، یک مسألۀ جستجو است. تلاش یک سپاه در حال جنگ، برای وارد کرد بیشترین خسارات بر دشمن با از دست دادن کمترین نیرو و جنگ‌افزار، یا کوشش یک دانش‌آموز برای دست یافتن به بالاترین نمره، سعی یک موسیقیدان یا نگارگر برای خلق زیباترین اثر هنری، تلاش یک کاندیدا برای به دست آوردن بیشترین رأی، طراحی یک نجّار برای ساختن راحت‌ترین صندلی، تلاش و نقشه چینی ورزشکاران و مربّیان برای یافتن راه‌های پیروزی بر حریف و... همگی جستجویی در فضای یک مسأله برای یافتن نقاط یا ناحیه بهینگی (بیشینه یا کمینه) هستند و همین امر موجب پیشرفت تمدن و آفرینش شده است.

در دانش کامپیوتر و فناوری  اطلاعات هم «جستجو» یکی از مهمترین مسائل است. تنها کافیست که حجم اطلاعات قرار گرفته بر حافظه‌های گوناگون و اینترنت را در نظر بگیریم تا جایگاه ویژه آن را دریابیم.

تاکنون روشهای بسیاری توسط طراحان الگوریتم‌ها برای انجام جستجو بر داده‌های دیجیتالی ارائه شده است. روش‌هایی به نام جستجوی سریع  و جستجوی دودویی ، از ساده‌ترین الگوریتم‌هایی هستند که دانشجویان گرایش‌های مهندسی کامپیوتر در نخستین سال‌های دوره کارشناسی فرا می‌گیرند، امّا این الگوریتم‌ها شاید، هنگامی که با حجمی گسترده از داده‌ها روبرو شوند، کارایی ندارند و حتی الگوریتم‌های پیشرفته‌تر مانند جستجوی بازپخت شبیه‌سازی شده  و الگوریتم عمیق‌شوندۀ‌ تکراری  نیز در هنگام رویارویی با مسائل ابرفضا   از یافتن راه‌حل یا ناحیه‌های دلخواه در می‌مانند. در این میان یک روش جادویی وجود وجود دارد که مسائل بزرگ را به سادگی و به گونه‌ای شگفت‌انگیز حل می‌کند و آن «الگوریتم ژنتیک»   است. ناگفته پیداست که واژۀ «الگوریتم ژنتیک» از دو واژۀ «الگوریتم»  و «ژنتیک» تشکیل شده است که خود مبیّن این مطلب است که این روش از دو علم ریاضی و زیست‌شناسی برای حل مسائل کمک می‌گیرد.

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


1-3- ایدۀ اصلی استفاده از الگوریتم ژنتیک
در دهه 70 میلادی دانشمندی از دانشگاه میشیگان به نام «جان هلند»  ایده استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. (ژن ها قطعاتی از یک کروموزوم هستند که اطلاعات مورد نیاز برای یک مولکول DNA یا یک پلی پپتید را دارند. علاوه بر ژنها، انواع مختلفی از توالی‌های مختلف تنظیمی در روی کروموزوم‌ها وجود دارد که در همانندسازی، رونویسی و... شرکت دارند. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم‌های او به نسل بعدی منتقل می‌شوند. هر ژن در این کروموزوم‌ها نماینده یک خصوصیت است. بعنوان مثال ژن 1 می‌تواند رنگ چشم باشد، ژن 2 طول قد، ژن 3 رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود.

بدیهی است که در عمل چنین اتفاقی رخ نمی‌دهد. در واقع بصورت همزمان دو اتفاق برای کروموزوم‌ها می‌افتد. اتّفاق اول موتاسیون(جهش) است. موتاسیون به این صورت است که بعضی ژن‌ها بصورت کاملاً تصادفی تغییر می‌کنند. البته تعداد اینگونه ژن‌ها بسیار کم می‌باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلاً ژن رنگ چشم می‌تواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد، در حالی که تمامی نسل قبل دارای چشم قهوه‌ای بوده‌اند. علاوه بر موتاسیون اتفاق دیگری که می‌افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به موتاسیون رخ می‌دهد چسبیدن ابتدای یک کروموزوم به انتهای یک کروموزوم دیگر است.  این همان چیزیست که مثلاً باعث می‌شود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری می‌کند.

حال می‌توانیم اینگونه بیان کنیم که: الگوريتم ژنتيک ابزاری می‌باشد که توسط آن ماشين می‌تواند مكانيزم انتخاب طبيعی را شبيه سازی نمايد. اين عمل با جستجو در فضای مسأله جهت يافتن جواب برتر و نه الزاماً بهينه صورت می‌پذيرد. الگوریتم ژنتیک را می‌توان یک روش جستجوی کلّی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید می کند. در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون  هستند.


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

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


1-5- تاریخچه علم ژنتیک
اوّلین کسی که توانست قوانین حاکم بر انتقال صفات ارثی را شناسایی کند، کشیشی اتریشی به نام «گریگور مندل»  بود که در سال ۱۸۶۵ این قوانین را که حاصل آزمایشاتش روی گیاه نخودفرنگی بود، ارائه کرد. وی با ترکیب نژادهای گوناگون، نتایجی در مورد اثر متقابل خصوصیات به دست آورد. به عنوان مثال وقتی که گیاهان بلند را با گیاهان کوتاه ترکیب می‌کرد، بدون توجّه به اینکه کدامیک، گرده را اهداء کرده، فرزندان همه بلند می‌شدند. «مندل» نتیجه گرفت که خاصیت گیاه بلند (یا همان ژن که بعدها شناخته شد) پیروز شده و خاصیت گیاه کوتاه کنار گذاشته شده است. اما متأسفانه جامعۀ علمی آن دوران به دیدگاه‌ها و کشفیات او اهمیّت چندانی نداد و نتایج کارهای «مندل» به دست فراموشی سپرده شد. در سال ۱۹۰۰ میلادی کشف مجدّدِ قوانین ارائه شده از سوی «مندل»، توسط «درویس»، «شرماک» و «کورنز» باعث شد که نظریات او مورد توجه و قبول قرار گرفته و «مندل» به عنوان پدر علم ژنتیک شناخته شود.

در سال ۱۹۵۳ با کشف ساختمان جایگاه ژن‌ها از سوی «جیمز واتسون»  و «فرانسیس کریک» ، رشته‌ای جدید در علم زیست‌شناسی بوجود آمد که زیست‌شناسی مولکولی نام گرفت. با حدود گذشت یک قرن از کشفیات «مندل» در خلال سال‌های ۱۹۷۱ و ۱۹۷۳ در رشته زیست‌شناسی مولکولی و ژنتیک که اوّلی به برّرسی ساختمان و مکانیسم عمل ژن‌ها و دوّمی به برّرسی بیماری‌های ژنتیک و پیدا کردن درمانی برای آنها می‌پرداخت، ادغام شدند و رشته‌ای به نام «مهندسی‌ژنتیک»  را بوجود آوردند که طی اندک زمانی توانست رشته‌های مختلفی اعم از پزشکی، صنعت و کشاورزی را تحت‌الشّعاع خود قرار دهد.


1-6- تکامل طبیعی (قانون انتخاب طبیعی داروین)
هنگامی که لغت تنازع بقا به کار می‌رود اغلب بار ارزشی منفی آن به ذهن می‌آید. شاید همزمان قانون جنگل به ذهن برسد و حکم بقای قوی‌ترها!

البته همیشه هم قوی‌ترین‌ها برنده نبوده‌اند. مثلاً دایناسورها با وجود جثّه عظیم و قوی‌تر بودن در طی روندی کاملاً طبیعی بازیِ بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف‌تر از آنها حیات خویش را ادامه دادند. ظاهراً طبیعت، بهترین‌ها را تنها بر اساس هیکل انتخاب نمی‌کند! در واقع درست‌تر آنست که بگوییم طبیعت مناسب‌ترین‌ها را انتخاب می‌کند نه بهترین‌ها.

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

برای نمونه می‌توان گفت که: در میان یک گلّه گرگ با افرادِ دارای ژن‌های گوناگون، گرگی احتمال بقای بالاتر را دارد که قوی‌تر از دیگران است، چراکه هم امکان بیشتری برای جفت‌گیری و گسترش ژن خود را دارد و هم بیش از گرگ‌های ضعیف‌تر به شکار دست یافته، زنده می‌ماند. در یک گلّه گوزن نیز وضع به همین شکل است: گوزن ضعیف‌تر هم کمتر امکان تولید مثل می‌یابد و هم زودتر توسّط درندگان گرفتار می‌آید.

و یا در مثالی دیگر، فرض کنید گونۀ خاصی از افراد، هوش بیشتری از بقیه افرادِ یک جامعه دارند. در شرایط کاملاً طبیعی، این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتاً بالاتری خواهند داشت و این رفاه، خود باعث طول عمر بیشتر و باروری بهتر خواهد بود (توجه کنید شرایط، طبیعیست نه در یک جامعه سطح بالا با ملاحظات امروزی؛ یعنی طول عمر بیشتر در این جامعۀ نمونه با زاد و ولد بیشتر همراه است). حال اگر این خصوصیّت (هوش) ارثی باشد بالطّبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشترِ این‌گونه افراد، بیشتر خواهد بود. اگر همین روند را ادامه دهید خواهید دید که در طی نسل‌های متوالی دائماً جامعۀ نمونۀ ما باهوش و باهوش‌تر می‌شود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملاً افراد کم‌هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائماً در حال افزایش است.

بدین ترتیب می‌توان دید که طبیعت با بهره‌گیری از یک روش بسیار ساده (حذف تدریجی گونه‌های نامناسب و در عین حال تکثیر بالاتر گونه‌های بهینه)، توانسته است دائماً هر نسل را از لحاظ خصوصیّات مختلف ارتقاء بخشد.

البتّه آنچه در بالا ذکر شد به تنهایی توصیف کنندۀ آنچه واقعاً در قالب تکامل در طبیعت اتفاق می‌افتد نیست. بهینه‌سازی و تکامل تدریجی به خودی خود نمی‌تواند طبیعت را در دسترسی به بهترین نمونه‌ها یاری دهد. اجازه دهید تا این مسأله را با یک مثال شرح دهیم:

پس از اختراع اتومبیل به تدریج و در طیّ سال‌ها اتومبیل‌های بهتری با سرعت‌های بالاتر و قابلیت‌های بیشتر نسبت به نمونه‌های اولیه تولید شدند. طبیعیست که این نمونه‌های متأخّر حاصل تلاش مهندسانِ طرّاح جهت بهینه‌سازی طرّاحی‌های قبلی بوده‌اند. اما دقّت کنید که بهینه‌سازی یک اتومبیل، تنها یک «اتومبیل بهتر» را نتیجه می‌دهد.

اما آیا می‌توان گفت اختراع هواپیما نتیجه همین تلاش بوده است؟ یا فرضاً می‌توان گفت فضا‌پیماها حاصل بهینه‌سازی طرح اولیه هواپیماها بوده‌اند؟

پاسخ اینست که گرچه اختراع هواپیما قطعاً تحت تأثیر دستاورهای صنعت اتومبیل بوده است؛ اما به‌هیچ‌وجه نمی‌توان گفت که هواپیما صرفاً حاصل بهینه‌سازی اتومبیل و یا فضا‌پیما حاصل بهینه‌سازی هواپیماست. در طبیعت هم عیناً همین روند حکم‌فرماست. گونه‌های متکامل‌تری وجود دارند که نمی‌توان گفت صرفاً حاصل تکامل تدریجی گونه قبلی هستند.

در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مسأله یاری کند مفهومیست به نام تصادف یا جهش. به عبارتی طرح هواپیما نسبت به طرح اتومبیل یک جهش بود و نه یک حرکت تدریجی. در طبیعت نیز به همینگونه ‌است. در هر نسل جدید بعضی از خصوصیات به صورتی کاملاً تصادفی تغییر می‌یابند سپس بر اثر تکامل تدریجی که پیشتر توضیح دادیم در صورتی که این خصوصیت تصادفی شرایط طبیعت را ارضاء کند حفظ می‌شود در غیر این‌صورت به شکل اتوماتیک از چرخه طبیعت حذف می‌گردد.
در واقع می‌توان تکامل طبیعی را به این‌صورت خلاصه کرد: جست‌وجوی کورکورانه (تصادف) + بقای قوی‌تر.


1-7- رابطه تکامل طبیعی با روش‌های هوش مصنوعی
حال ببینیم که رابطه تکامل طبیعی با روش‌های هوش مصنوعی چیست. هدف اصلی روش‌های هوشمندِ به کار گرفته شده در هوش مصنوعی، یافتن پاسخ بهینه مسائل مهندسی است. بعنوان مثال اینکه چگونه یک موتور را طراحی کنیم تا بهترین بازدهی را داشته باشد یا چگونه بازوهای یک ربات را متحرک کنیم تا کوتاه‌ترین مسیر را تا مقصد طی کند (دقت کنید که در صورت وجود مانع یافتن کوتاه‌ترین مسیر دیگر به سادگی کشیدن یک خط راست بین مبدأ و مقصد نیست) همگی مسائل بهینه‌سازی هستند.

روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی  را بعنوان نقطه بهینه کلی  در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مسأله خاصی کاربرد دارند. این دو نکته را با مثال‌های ساده‌ای روشن می‌کنیم.

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

شکل 1-1-نقاط بهینۀ محلی و بهینۀ کلی

در مورد نکته دوم باید بگوییم که روش‌های ریاضی بهینه‌سازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مسأله می‌شوند (تنها برای مسأله خاصی کاربرد دارند)، در حالی که روش‌های هوشمند دستورالعمل‌هایی هستند که به صورت کلی می‌توانند در حل هر مسأله‌ای به کار گرفته شوند. این نکته را پس از آشنایی با خود الگوریتم بیشتر و بهتر خواهید دید.



الگوریتم ژنتیک، هیوریستیک، ترکیب و جهش، تکامل طبیعی داروین، معمای هشت وزیر، پیشگامان متا، meta4u.com

[Zohreh Gholami]

1-8- الگوریتم
در علوم کامپیوتر و ریاضیات، یک الگوریتم جستجو، الگوریتمی است که یک مسأله را به عنوان ورودی می‌گیرد و بعد از ارزیابی کردن راه‌حل‌های ممکن، یک راه‌حل برای آن مسأله برمی‌گرداند. هنگامی که مسأله‌ای را حل می‌کنیم معمولاً دنبال آن هستیم که بهترین راه‌حل و یا به بیان دیگر به یک حلّ بهینه از بین حل‌های ممکن برای مسأله برسیم. به محدوده‌ای که جواب‌های مسأله قابل قبول می‌باشند به طوری که جواب بهینه هم یکی از زیرمجموعه‌های این محدوده است «فضای جستجو»  نامیده می‌شود. هر نقطه از محدودۀ فضای جستجو نشان دهندۀ یکی از روش‌های حلّ مسأله می‌باشد. و یا به بیانی ساده‌تر می‌توان گفت: مجموعۀ راه‌حل‌های ممکن برای یک مسأله را فضای جستجو می‌نامند.

مهم ترين عامل در حل هر مسأله، جستجو به دنبال پاسخ‌هاي احتمالي مسئله است. به طور کلّی با دو دسته از الگوریتم‌ها مواجه هستیم؛ بعضی از الگوریتم‌ها که با عنوان الگوریتم‌های ناآگاهانه شناخته می‌شوند الگوریتم‌هایی هستند که از روش‌های ساده‌ای برای جستجوی فضای نمونه استفاده می‌کنند. در حالی که الگوریتم‌های آگاهانه با استفاده روش‌هایی مبتنی بر دانش در بارۀ ساختار فضای جستجو، می‌کوشند تا زمان جستجو را کاهش دهند.

در کتاب «راسل» این الگوریتم‌ها به شکل زیر رده‌بندی شده‌اند:
•   الگوریتم‌های ناآگاهانه
•   الگوریتم‌های آگاهانه


1-8-1- الگوریتم‌های جستجوی ناآگاهانه
یک الگوریتم جستجوی ناآگاهانه الگوریتمی است که به ماهیّت مسأله کاری ندارد. از این‌رو می‌توانند به طور عمومی طراحی شوند و از همان طراحی برای محدودۀ عظیمی از مسائل استفاده کنند، این امر نیاز به طراحی انتزاعی دارد. از جمله مشکلاتی که این چنین الگوریتم‌هایی دارند این است که اغلب فضای جستجو بسیار بزرگ است و نیازمند زمان زیادی (حتی برای نمونه‌های کوچک) می‌باشد. از این‌رو برای بالا بردن سرعت پردازش غالبا از الگوریتم‌های آگاهانه استفاده می‌کنند.


1-8-1-الف- جستجوی لیست
الگوریتم‌های جستجویِ لیست شاید از ابتدایی‌ترین انواع الگوریتم‌های جستجو باشند. هدف آن پیدا کردن یک عنصر از مجموعه‌ای از کلیدهاست (ممکن است شامل اطلاعات دیگری مرتبط با آن کلید نیز باشد). ساده‌ترین این الگوریتم‌ها، جستجوی خطّی است که هر عنصر از لیست را با عنصر مورد نظر مقایسه می‌کند. زمان اجرای این الگوریتم از O(n) است وقتی که n تعداد عناصر در لیست باشد. اما می‌توان از روش دیگری استفاده کرد که نیازی به جستجوی تمام لیست نباشد. جستجوی دودویی اندکی از جستجوی خطّی بهتر است. زمان اجرای آن از O(log n) است. این روش برای لیستی با تعداد دادۀ زیاد بسیار کارآمدتر از روش جستجوی خطّی است. اما در این روش لیست باید قبل از جستجو مرتب شده باشد. «جستجو با میان‌یابی» برای داده‌های مرتب شده با تعداد زیاد و توزیع یکنواخت، مناسب‌تر از جستجوی دودویی است. زمان اجرای آن به طور متوسّط O(log(log n)) است ولی بدترین زمان اجرای آن O(n) می‌باشد. الگوریتم «گراور»  الگوریتم پلّه‌ای است که برای لیست‌های مرتب نشده استفاده می‌شود. الگوریتم Hash Table نیز برای جستجوی لیست به کار می‌رود. به طور متوسط زمان اجرای ثابتی دارد. اما نیاز به فضای اضافه داشته و بدترین زمان اجرای آن از O(n) است.


1-8-1-ب- جستجوی درختی
الگوریتم‌های جستجوی درختی، قلب شیوه‌های جستجو برای داده‌های ساخت یافته هستند. مبنای اصلی جستجوی درختی، گره‌هایی است که از یک ساختمان داده گرفته شده‌اند. هر عنصر که بخواهد اضافه شود با داده‌های موجود در گره‌های درخت مقایسه می‌شود و به ساختار درخت اضافه می‌شود. با تغییر ترتیب داده‌ها و قرار دادن آنها در درخت، درخت با شیوه‌های مختلفی جستجو می‌شود. برای مثال سطح به سطح (جستجوی نخست-پهنا) یا پیمایش معکوس درخت (جستجوی نخست-ژرفا). از مثال‌های دیگر جستجوهای درختی می‌توان به جستجوی عمقی تکرار شونده، جستجوی عمقی محدود شده، جستجوی دوطرفه و جستجوی هزینه یکنواخت اشاره کرد.


1-8-1-پ- جستجوی گراف
بسیاری از مسائل در نظریۀ گراف می‌تواند با الگوریتم‌های پیمایش درخت حل شوند، مثل الگوریتم دیکسترا ، الگوریتم کروسکال ، الگوریتم نزدیک‌ترین‌همسایه  و الگوریتم پریم . می‌توان این الگوریتم‌ها را توسعه یافتۀ الگوریتم‌های جستجوی درختی دانست.



1-8-2- الگوریتم‌های جستجوی آگاهانه
در یک جستجوی آگاهانه، از نوع خاصی از مسائل به عنوان راهنما استفاده می‌شود. یک گونۀ خوب، یک جستجوی آگاهانه با کارایی قابل توجّهی نسبت به جستجوی ناآگاهانه به وجود می‌آورد. الگوریتم‌های برجستۀ کمی از جستجوی آگاهانۀ یک لیست وجود دارد. یکی از این الگوریتم‌ها Hash Table با یک تابع Hash که برمبنای نوع مسأله‌ای که دردست است می‌باشد. بیشتر الگوریتم‌های جستجوی آگاهانه، بسطی از درخت‌ها هستند. همانند الگوریتم‌های ناآگاهانه، این الگوریتم‌ها برای گراف‌ها نیز می‌توانند به کار روند.

دليل نياز به روش‌هاي جستجوي آگاهانه، نياز به كاهش هزينۀ زماني مورد نياز براي حلّ مسأله است. در واقع به اين دليل كه ما تمايل داريم مسائل را در زمان كمتري حل كرده و از بررسي تمام حالات ممكن اجتناب كنيم، مي‌بايست روشي براي تشخيص كيفيت مسير (حتي به شكل نسبي) داشته باشيم.


1-8-2-الف- جستجوی خصمانه
در یک بازی مثل شطرنج، یک درخت بازی شامل تمام حرکات ممکن توسط هر دو بازیکن و نتایج حاصل از ترکیب این حرکات وجود دارد، و ما می‌توانیم این درخت را جستجو کرده و مؤثرترین استراتژی برای بازی را بیابیم. این چنین مسائلی دارای مشخصۀ منحصر به فردی هستند. برنامه‌های بازی‌های رایانه‌ای، و همچنین فرم‌های هوش مصنوعی مثل برنامه‌ریزی ماشین‌ها، اغلب از الگوریتم‌های جستجو مثل الگوریتم مین‌ماکس  (می‌نیمیم مجموعه‌ای از ماکزیمم‌ها)، هرس کردن درخت جستجو و هرس کردن آلفا-بتا استفاده می‌کنند.



1-9- مسائل NP-Hard
نمونه‌ای از مسائلی که نمی‌توان آنها را به روش سنتی حل کرد مسائل NP هستند. مجموعه «ان‌پی-سخت» شامل چندهزار مسأله مختلف با کاربردهای فراوان است که تاکنون برای آنها راه‌حلّ سریع و قابل انجام در زمان معقول پیدا نشده ‌است و به احتمال زیاد در آینده نیز یافت نخواهد شد. این که راه‌حلّ سریعی برای آنها وجود ندارد هم اثبات شده‌است. البته ثابت شده ‌است که اگر فقط برای یکی از این مسأله‌ها راه‌حل سریعی پیدا شود، این راه‌حل موجب حلّ سریع بقیۀ مسأله‌ها خواهد شد. البته احتمال پیدا شدن چنین الگوریتمی ضعیف است. منظور از راه‌حلّ سریع آن است که زمان اجرای آن با اندازۀ ورودی مسأله به صورت چندجمله‌ای رابطه داشته باشد.

روش‌های مختلفی برای حلّ سریع ولی نزدیک به بهینه برای یک مسألۀ NP-Hard وجود دارد:
• راه حلّ تقریبی قابل اثبات(الگوریتم‌های تقریبی): که در آن یک الگوریتم سریع برای حلّ مسأله ارائه می‌شود ولی اثبات می‌شود که اندازۀ خروجی ضریبی از اندازۀ خروجی بهینۀ مسأله ‌است.
• الگوریتم‌های مکاشفه‌ای: با این که الگوریتم‌هایی سریع هستند و به صورت تقریبی جواب را به دست می‌آورند، اما در مورد ضریب تقریب یا میزان خوبی الگوریتم اثباتی وجود ندارد. بسیاری از این الگوریتم‌ها به صورت تجربی آزمایش می‌شوند. برخی از این الگوریتم‌ها از «روش حریصانه» برای حل استفاده می‌کنند.
راه‌های معمول مقابله با چنین مسائلی عبارتند از:
• طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
• استفاده از «الگوریتم‌های مکاشفه‌ای»  که جواب‌هایی به‌دست می‌دهد که احتمالاً درست هستند.
• پیدا کردن زیرمسأله‌هایی از مسأله، یعنی تقسیم مسأله به مسأله‌های کوچکتر.

دو مسأله زیر جزءِ مسائل NP-Hard می‌باشند:
• مسئله فروشنده دوره‌گرد
• مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل)

اما مسائل مهم زیادی نیز وجود دارند که یافتن راه‌حل در آنها بسیار دشوار است. اما اگر راه‌حل را داشته باشیم، بررسی آن آسان می‌شود. این واقعیت منجر به مسائل NP-Complete problems  شد.NP معرف Nondeterministic  (چند جمله‌ای‌های غیرجبری) و به این معناست که امکان این وجود که راه‌حل را حدس زد و سپس آن را بررسی کرد.

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

امروزه، هیچکس نمی‌داند که آیا الگوریتم سریعتری برای یافتن جواب دقیق در مسائل NP  وجود دارد یا خیر. و یافتن چنین الگوریتمی وظیفه مهمی است که به عهده محققان می‌باشد. امروزه اکثر مردم تصور می‌کنند که چنین الگوریتمی وجود ندارد و بنابراین به دنبال روش دیگری (جایگزین) هستند. و نمونه‌ای از روش جایگزین، الگوریتم ژنتیکی است.



1-10- هیوریستیک
سیستم‌های پیچیده اجتماعی، تعداد زیادی از مسائلِ دارایِ طبیعتِ ترکیباتی را پیش روی ما قرار می‌دهند. مسیر کامیون‌های حمل‌ونقل باید تعیین شود، انبارها یا نقاط فروش محصولات باید جایابی شوند، شبکه‌های ارتباطی باید طراحی شوند، کانتینرها باید بارگیری شوند، رابط‌های رادیویی می‌بایست دارای فرکانس مناسب باشند، مواد اولیه چوب، فلز، شیشه و چرم باید به اندازه‌های لازم بریده شوند؛ از این دست مسائل بی‌شمارند. تئوری پیچیدگی به ما می‌گوید که مسائلِ ترکیباتی اغلب چندجمله‌ای  نیستند. این مسائل در اندازه‌های کاربردی و عملی خود به قدری بزرگ هستند که نمی‌توان جواب بهینۀ آنها را در مدّت زمان قابل پذیرش به دست آورد. با این وجود، این مسائل باید حل شوند و بنابراین چاره‌ای نیست که به جواب‌های زیر بهینه بسنده نمود؛ به گونه‌ای که دارای کیفیّت قابل پذیرش بوده و در مدّت زمان قابل پذیرش به دست آیند. چندین رویکرد برای طراحی جواب‌های با کیفیّت قابل پذیرش تحت محدودیّت زمانی قابل پذیرش پیشنهاد شده است.

الگوریتم‌هایی وجود دارند که می‌توانند یافتن جواب‌های خوب در فاصله مشخصی از جواب بهینه را تضمین کنند که به آنها الگوریتم‌های تقریبی می‌گویند. الگوریتم‌های دیگری هستند که تضمین می‌دهند با احتمال بالا جواب نزدیک بهینه تولید کنند که به آنها الگوریتم‌های احتمالی گفته می‌شود. جدای از این دو دسته، می‌توان الگوریتم‌هایی را پذیرفت که هیچ تضمینی در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتایج آنها، به طور متوسط بهترین تقابل کیفیت و زمان حل برای مسأله مورد بررسی را به همراه داشته‌اند؛ به این الگوریتم‌ها، الگوریتم‌های هیوریستیک گفته می‌شود.

هیوریستیک‌ها عبارتند از معیارها، روشها یا اصولی برای تصمیم‌گیری بین چندین خط‌مشی و انتخاب اثربخش‌ترین برای دستیابی به اهداف موردنظر. هیوریستیک‌ها نتیجۀ برقراری اعتدال بین دو نیاز هستند: نیاز به ساخت معیار‌های ساده و در همان زمان توانایی تمایز درست بین انتخاب‌های خوب و بد.

یک هیوریستیک می‌تواند حسابی سرانگشتی باشد که برای هدایت یک دسته از اقدامات به کار می‌رود. برای مثال، یک روش مشهور برای انتخاب طالبی رسیده عبارتست از فشار دادن محل اتصال به ریشه از یک طالبی نامزدِ انتخاب و سپس بو کردن آن محل؛ اگر بوی آن محل مانند بوی داخل طالبی باشد آن طالبی به احتمال زیاد رسیده است. این قاعده سرانگشتی نه تضمین می‌کند که تنها طالبی‌های رسیده به عنوان نامزد انتخاب شوند و نه تضمین می‌کند که طالبی‌های رسیده آزمایش‌شده، رسیده تشخیص داده شوند اما به هر حال این روش، اثربخش‌ترین روش شناخته شده است.

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

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


1-10-1- انواع الگوریتم‌های هيوریستیک
در حالت کلی سه دسته از الگوریتم‌های هیوریستیک قابل تشخیص است:
1- الگوریتم‌هایی که بر ویژگی‌های ساختاری مسأله و ساختار جواب متمرکز می‌شوند و با استفاده از آنها الگوریتم‌های سازنده یا جستجوی محلی تعریف می‌کنند.
2- الگوریتم‌هایی که بر هدایت هیوریستیک یک الگوریتم سازنده یا جستجوی محلی متمرکز می‌شوند به گونه‌ای که آن الگوریتم بتواند بر شرایط حساس (مانند فرار از بهینه محلی) غلبه کند. به این الگوریتم‌ها، متاهیوریستیک  گفته می‌شود.
3- الگوریتم‌هایی که بر ترکیب یک چارچوب یا مفهوم هیوریستیک با گونه‌هایی از برنامه‌ریزی ریاضی (معمولاً روش های دقیق) متمرکز می‌شوند.

هیوریستیک‌های نوع اول می‌توانند خیلی خوب عمل کنند (گاهی اوقات تا حد بهینگی) اما ممکن است در جواب‌های دارای کیفیت پایین گیر کنند. همانطور که اشاره شد یکی از مشکلات مهمی که این الگوریتم‌ها با آن روبرو می‌شوند افتادن در بهینه‌های محلی است، بدون اینکه هیچ شانسی برای فرار از آنها داشته باشند. برای بهبود این الگوریتم‌ها از اواسط دهۀ 70، موج تازه‌ای از رویکردها آغاز گردید. این رویکردها شامل الگوریتم‌هایی است که صریحاً یا به صورت ضمنی تقابل بین ایجاد تنوع جستجو (وقتی علائمی وجود دارد که جستجو به سمت مناطق بد فضای جستجو می‌رود) و تشدید جستجو (با این هدف که بهترین جواب در منطقه مورد بررسی را پیدا کند) را مدیریت می‌کنند. این الگوریتم‌ها متاهیوریستیک نامیده می‌شوند.

از بین این الگوریتم‌ها می‌توان به موارد زیر اشاره کرد:
1- بازپخت شبیه‌سازی شده.
2- جستجوی ممنوع.
3- الگوریتم‌های ژنتیک.
4- شبکه‌های عصبی مصنوعی.
5- بهینه‌سازی مورچه‌ای یا الگوریتم‌های مورچه.

که در این بین الگوریتم‌های ژنتیک از شهرت بیشتری نسبت به دیگر الگوریتم‌ها برخوردار است.

[Zohreh Gholami]

فصل دوم:
الگوریتم ژنتیک



2-1- مقدمه
الگوریتم‌های ژنتیک یکی از اعضای خانوادۀ مدل‌های محاسباتی الهام گرفته شده از روند تکامل است. این الگوریتم‌ها راه‌حل‌های بالقوّۀ یک مسأله را در قالب کروموزوم‌های ساده‌ای کد می‌کنند و سپس عملگرهای ترکیبی را بر روی این ساختارها اِعمال می‌کنند. الگوریتم‌های ژنتیک اغلب به عنوان روشی برای بهینه‌سازی توابع شناخته می‌شوند که البته دامنۀ استفاده از این روش‌ها بسیار گسترده‌تر از این است.

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


2-2- الگوریتم ژنتیک
الگوریتم ژنتیک که روش بهینه‌سازی الهام گرفته از طبیعت جاندار(موجودات زنده) است که می‌توان در طبقه‌بندی‌ها، از آن به عنوان یک روش عددی، جستجوی مستقیم و تصادفی یاد کرد. این الگوریتم، الگوریتمی مبتنی بر تکرار است و اصول اولیۀ آن همانطور که پیشتر اشاره شد از علم ژنتیک اقتباس گردیده است و با تقلید از تعدادی از فرآیندهای مشاهده شده در تکامل طبیعی اختراع شده است و به طور موثّری از معرفت قدیمی موجود در یک جمعیت استفاده می‌کند، تا حل‌های جدید و بهبود یافته را ایجاد کند. این الگوریتم در مسائل متنوعی نظیر بهینه‌سازی، شناسایی و کنترل سیستم، پردازش تصویر و مسایل ترکیبی، تعین توپولوژی و آموزش شبکه‌های عصبی مصنوعی و سیستم‌های مبتنی بر تصمیم و قاعده به کار می‌رود.

در اینجا لازم می‌بینم که برای ورود به موضوع اصلی این نوشتار (الگوریتم ژنتیک) مروری بر مطالبی که پیشتر در مورد مباحث «ژنتیک» و «الگوریتم» ارائه شد داشته باشیم.

چنان که قبل‌تر اشاره شد، علم ژنتیک، علمی است که دربارۀ چگونگی توارث و انتقال صفحات بیولوژیکی از نسلی به نسل بعد صحبت می‌کند. عامل اصلی انتقال صفحات بیولوژیکی در موجودات زنده کروموزوم‌ها  و ژن‌ها  می‌باشد و نحوه عملکرد آنها به گونه‌ای است که در نهایت ژن‌ها و کروموزوم‌های برتر و قوی مانده و ژن‌هاي ضعيف‌تر از بين مي‌روند. به عبارت ديگر نتيجۀ عمليات متقابل ژن‌ها و كروموزوم‌‌ها باقي ماندن موجودات اَصلح و برتر مي‌باشد.

همچنین مجدداً یادآور می‌شویم که اين الگوريتم براي بهينه سازي، جستجو و يادگيري ماشين مورد استفاده قرار مي‌گيرد. اساس اين الگوريتم قانونِ تكاملِ داروين (بقا بهترين) است كه مي‌گويد: موجودات ضعيف‌تر از بين مي‌روند و موجودات قوي‌تر باقي مي‌مانند. در واقع تكامل فرآيندي است كه روي رشته‌ها صورت مي‌گيرد، نه روي موجودات زنده‌اي كه معرف موجودات رشته است. در واقع، قانون انتخاب طبيعي براي بقا مي‌گويد كه هر چه امكان تطبيق موجود بيشتر باشد بقاي موجود امكان‌پذيرتر است و احتمال توليد مثل بيشتري، برايش وجود دارد. اين قانون بر اساس پيوند بين رشته‌ها و عملكرد ساختمان‌هاي رمزگشايي شده آنها مي‌باشد.


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

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

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

• الگوريتم ژنتيك در هر تكرار چند نقطه از فضاي جستجو را در نظر مي‌گيرد بنابراين شانس اينكه به يك ماكزيمم محلي همگرا شود كاهش مي‌يابد.
در بيشتر روش‌هاي جستجوي مرسوم (روش گراديان) قاعده تصميم حاكم به اين صورت عمل مي‌كند كه از اين يك نقطه به نقطه ديگر حركت مي‌كند. اين روش‌ها مي‌توانند در فضاهاي جستجو داراي چند بيشينۀ خطرناك باشند. زيرا ممكن است آنها به يك ماکزيمم محلي همگرا شوند. ليكن الگوريتم ژنتيك جمعيت‌هاي كاملي از رشته‌ها (نقاط) را توليد مي‌كند سپس هر نقطه را به صورت انفرادي امتحان مي‌كند و با تركيب محتويات آنها يك جمعيت جديد را كه شامل نقاط بهبود يافته است تشكيل مي‌دهد. صرف نظر از انجام يك جستجو ملاحظۀ هم‌زمانِ تعدادي نقطه در الگوريتم ژنتيك آنها را با ماشين‌هاي موازي تطبيق مي‌سازد زيرا در اينجا تكامل هر نقطه يك فرآيند مستقل است. لذا الگوريتم ژنتيك فقط نياز به اطلاعاتي در مورد كيفيت حل‌هاي ايجاد شده به وسيلۀ هر مجموعه از متغيرها دارد، در صورتي كه بعضي از روش‌هاي بهينه‌سازي نياز به اطلاعات يا حتي نياز به شناخت كامل از ساختمان مسأله و متغيرها دارند. چون الگوريتم ژنتيك نياز به چنين اطلاعات مشخصي از مسأله ندارد بنابراين قابل انعطاف‌تر از بيشتر روش‌هاي جستجو است. همچنين الگوريتم ژنتيك از روش‌هاي جستجوي نوعي كه براي راهنمايي جهت روش‌هاي جستجويشان از انتخاب تصادفي استفاده مي‌كنند متفاوت است زيرا اگر چه براي تعريف روش‌هاي تصميم‌گيري از تصادف و شانس استفاده مي‌كند ولي در فضاي جستجو به صورت تصادفي قدم نمي‌زند.

•الگوریتم ژنتیک از قوانین احتمالی پیروی می‌کند و نه از قوانین قطعی.


2-3- مكانيزم الگوريتم ژنتيك
الگوريتم ژنتيك به عنوان يك الگوريتم محاسباتيِ بهينه‌سازي با در نظر گرفتن مجموعه‌اي از نقاط فضاي جواب در هر تكرار محاسباتي به نحو مؤثري نواحي مختلف فضاي جواب را جستجو مي‌كند. در مكانيزم جستجو گرچه مقدار تابع هدف تمام فضاي جواب محاسبه نمي‌شود ولي مقدار محاسبه شده تابع هدف براي هر نقطه، در متوسط‌گيري آماري تابع هدف براي هر نقطه، در متوسط‌گيري آماري تابع هدف در كليه زير فضاهايي كه آن نقطه به آنها وابسته بوده دخالت داده مي‌شود و اين زير فضاها به طور موازي از نظر تابع هدف متوسط‌گيري آماري مي‌شوند. اين مكانيزم را توازي ضمني  مي‌گويند. اين روند باعث مي‌شود كه جستجوي فضا به نواحي از آن كه متوسط آماري تابع هدف در آنها زياد بوده و امكان وجود نقطه بهينه مطلق در آنها بيشتر است سوق پيدا كند. چون در اين روش برخلاف روش‌هاي تك‌مسيري فضاي جواب به طور همه جانبه جستجو مي‌شود، امكان كمتري براي همگرايي به يك نقطه بهينه محلي وجود خواهد داشت.

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

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

مكانيزم‌هاي تصادفي كه روي انتخاب و حذف رشته‌ها عمل مي‌كنند به گونه‌اي هستند كه رشته‌هايي كه عدد برازندگي بيشتري دارند، احتمال بيشتري براي تركيب و توليد رشته‌هاي جديد داشته و در مرحله جايگزيني نسبت به ديگر رشته‌ها مقاوم‌تر هستند. بدين لحاظ جمعيت دنباله‌ها در يك رقابت بر اساس تابع هدف در طيّ نسل‌هاي مختلف، كامل شده و متوسط مقدار تابع هدف در جمعيت رشته‌ها افزايش مي‌يابد. بطور كلي در اين الگوريتم ضمن آنكه در هر تكرار محاسباتي، توسط عملگرهاي ژنتيكي نقاطي جديد از فضاي جواب مورد جستجو قرار مي‌گيرند توسط مكانيزم انتخاب، روند جستجوي نواحي از فضا را كه متوسط آماري تابع هدف در آنها بيشتر است، كنكاش مي‌كند. بر اساس سيكل اجرايي فوق، در هر تكرار محاسباتي، توسط عملگرهاي ژنتيكي نقاط جديدي از فضاي جواب مورد جستجو قرار مي‌گيرند توسط مكانيزم انتخاب، روند جستجو نواحي از فضا را كه توسط آماري تابع هدف در آنها بيشتر است، كنكاش مي‌كند. که بر این اساس، در هر تكرار محاسباتي، سه عملگر اصلي روي رشته‌ها عمل مي‌كند؛ اين سه عملگر عبارتند از: دو عملگر ژنتيكي و عملكرد انتخابي تصادفي.

«گلد برگ»  الگوريتم ژنتيكي «جان هولند» را با عنوان الگوريتم ژنتيك ساده  معرفي مي‌كند؛ الگوريتم ژنتيك را از الگوريتم ژنتيك طبيعي اقتباس كردند.

در فصل یک گفتیم که: بدن همه موجودات زنده از سلول‌ها تشكيل شده است و در هر سلولي دسته كروموزوم‌هاي يكساني وجود دارد. كروموزوم‌ها رشته‌هايي از DNA هستند كه در واقع الگويي براي تمام بدن هستند. هر كروموزومي محتوي دسته‌هايي DNA است كه ژن ناميده مي‌شوند و هر ژني پروتئين خاصي را رمزگذاري مي‌كند. اساساً مي‌توان گفت كه هر ژن، ويژگي خاصي (مثلا رنگ چشم) را رمزگذاري مي‌كند. حالت‌هاي مختلف يك خصيصه (آبي، قهوه‌اي) آلل   ناميده مي‌شود. هر ژني موقعيت خاص خود را بر روي كروموزوم دارد كه اين موقعيت لوكاس  ناميده مي‌شود. مجموعه كاملي از مواد ژنتيكي (همۀ كروموزوم‌ها) ژنوم ناميده مي‌شود. دستۀ خاصي از ژن‌هاي موجود در ژنوم، ژنوتيپ ناميده مي‌شود. ژنوتيپ به همراه تغييرات پس از تولّد، پايه و اساس فنوتيپ موجود زنده (ارگانيسم)، ويژگي‌هاي فيزيكي و ذهني از قبيل رنگ چشم و هوش و غيره است.

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

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

الگوريتم‌هاي ژنتيك، جستجوي اصلي را در فضاي پاسخ به اجرا مي‌گذارند. اين الگوريتم‌ها با توليد نسل  آغاز مي‌شوند كه وظيفه ايجاد مجموعه نقاط جستجوي اوليه به نام «جمعيت اوليه»  را بر عهده دارند و به طور انتخابي يا تصادفي تعيين مي‌شوند. از آنجايي كه الگوريتم‌هاي ژنتيك براي هدايت عمليات جستجو به طرف نقطه بهينه از روش‌هاي آماري استفاده مي‌كنند، در فرآيندي كه به انتخاب طبيعي وابسته است، جمعيت موجود به تناسب برازندگي افراد آن براي نسل بعد انتخاب مي‌شود. سپس عملگرهاي ژنتيكي شامل انتخاب ، پيوند(ترکیب)، جهش و ديگر عملگرهاي احتمالي اِعمال شده و جمعيت جديد به وجود مي‌آيد. پس از آن جمعيت جديدي جايگزين جمعيت پيشين مي‌شود و اين چرخه ادامه مي‌يابد.

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

[Zohreh Gholami]

2-4- عملگرهاي الگوريتم ژنتيك
به طور خلاصه الگوريتم ژنتيك از عملگرهاي زير تشكيل شده است:


2-4-1- کدگذاری
اين مرحله شايد مشكلترين مرحله حل مسأله به روش الگوريتم باشد. الگوريتم ژنتيك به جاي اينكه بر روي پارامترها يا متغيرهاي مسأله كار كند، با شكل كد شدۀ آنها سروكار دارد. يكي از روشهاي كد كردن، كد كردن دودويي مي باشد كه در آن هدف تبديل جواب مسأله به رشته‌اي از اعداد باينري (در مبناي 2) است.


2-4-2- ارزیابی
تابع برازندگي را از اِعمال تبديل مناسب بر روي تابع هدف يعني تابعي كه قرار است بهينه شود به دست مي‌آورند. اين تابع هر رشته را با يك مقدار عددي ارزيابي مي‌كند كه كيفيت آن را مشخص مي‌نمايد. هر چه كيفيت رشته جواب بالاتر باشد مقدار برازندگي جواب بيشتر است و احتمال مشاركت براي توليد نسل بعدي نيز افزايش خواهد يافت.


2-4-3- ترکیب
مهمترين عملگر در الگوريتم ژنتيك، عملگر ترکیب است. تركيب فرآيندي است كه در آن نسل قديمي كروموزوم‌ها با يكديگر مخلوط و تركيب مي‌شوند تا نسل تازه‌اي از كروموزوم‌ها بوجود بيايد.

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


2-4-4- جهش
جهش نيز عملگر ديگري هست كه جواب‌هاي ممكن ديگري را متولد مي‌كند. در الگوريتم ژنتيك بعد از اينكه يك عضو در جمعيت جديد بوجود آمد هر ژن آن با احتمال جهش، جهش مي‌يابد. در جهش ممكن است ژني از مجموعه ژن‌هاي جمعيت حذف شود يا ژني كه تا به حال در جمعيت وجود نداشته است به آن اضافه شود. جهش يك ژن به معناي تغيير آن ژن است و وابسته به نوع كدگذاري روش‌هاي متفاوت جهش استفاده مي‌شود.


2-4-5- رمزگشايي
رمزگشایی، عكسِ عمل رمزگذاری است. در اين مرحله بعد از اينكه الگوريتم بهترين جواب را براي مسأله ارائه كرد لازم است عكس عمل رمزگذاري روي جواب‌ها يا همان عمل رمزگشایی اعمال شود تا بتوانيم نسخه واقعي جواب را به وضوح در دست داشته باشيم.



2-5- چارت الگوريتم به همراه شبه كد آن
در حالت كلي وقتي يك الگوريتم ژنتيكي اعمال مي‌شود چرخه زير را طي مي‌كند:
ابتدا يك جمعيت اوليه از افراد به طور اتفاقي و بدون در نظرگرفتن معيار خاصي انتخاب مي‌شود. براي تمامي كروموزوم‌هاي(افراد) نسل صفر مقدار برازش با توجه به تابع پردازش كه ممكن است بسيار ساده يا پيچيده باشد تعيين مي‌شود. سپس با مكانيزم‌هاي مختلف تعريف شده براي عملگر انتخاب زيرمجموعه‌اي از جمعيت اوليه انتخاب خواهد شد. سپس روي اين افراد انتخاب شده عمليات برش و جهش در صورت لزوم با توجه به صورت مسأله اعمال خواهد شد.

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

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


2-5-1- شبه كد و توضيح آن
در اينجا الگوريتم ژنتيك به صورت شبه كد بيان شده است.

طرح كلي يك الگوريتم به شرح زير مي باشد:
1- آغاز: جمعيت n كروموزومي به صورت تصادفي ايجاد كنيد (راه‌حل‌هاي مناسب مسأله).
2- ارزش گذاري: برازندگي f(x) هر كروموزوم X در جمعيت را ارزيابي كنيد.
3- جمعيت جديد: جمعيت جديدي را تشكيل دهيد. مراحل زير را تكرار كنيد تا جمعيت جديد كامل شود:
انتخاب: دو كروموزوم (والدين) را با توجه به برازندگي آنها از ميان جمعيت انتخاب كنيد (هر چه برازندگي بيشتر باشد شانس انتخاب بيبشتر است.)
تركيب: با توجه به احتمال تركيب شدن  والدين را براي تشكيل فرزندان  جديد با هم تركيب كنيد.
جهش: با توجه به احتمال جهش  فرزندان را در هر لوکاس(موقعيت در كروموزوم)  مورد جهش قرار دهيد.
پذيرفتن: فرزندان جديد را در جمعيت جديد بگنجانيد.
جايگزيني: جمعيت جديد ايجاد شده را براي روند الگوريتم بكار ببريد.


2-5-2- چارت الگوریتم ژنتیک

شکل 2-1- چارت الگوریتم ژنتیک

2-6- تابع هدف
تابع هدف، هدف و خواستۀ ما از طرح مسأله است. یعنی، تابع هدف، شاخصی از نحوۀ عملکرد افراد در فضای مسأله می‌باشد.



2-7- روش‌های کد کردن
در این قسمت به بررسی کامل انواع کدینگ(کدگذاری) خواهیم پرداخت. هر چند همانطور که قبلاً هم گفته شد معمولاً از کد کردن دودویی استفاده می‌شود، اما در بسیاری از موارد کدینگ‌های دیگری به دلیل ماهیت مسأله مورد نیاز است.

انواع کدینگ (کدگذاری):
1- کدینگ باینری
2- کدینگ جایگشتی
3- کدینگ مقدار
4- کدینگ درختی

الگوریتم ژنتیک به جای این که بر روی پارامترها یا متغیرهای مسأله کار کند، با شکل کد شده آنها سروکار دارد. یکی از روش‌های کد کردن، کد کردن دودویی می‌باشد که در آن هدف تبدیل جواب مسأله به رشته‌ای از اعداد باینری (در مبنای 2) است.

تعداد بیت‌هایی که برای کد گذاری متغییر‌ها استفاده می‌شود، به دقت مورد نظر برای جواب‌ها، محدوده تغییر پارامترها و رابطه بین متغیرها وابسته است. رشته یا دنباله‌ای از بیت‌ها که به عنوان شکل کد شده یک جواب از مسأله مورد نظر می‌باشد، کروموزوم نامیده می‌شود. در حقیقت بیت‌های یک کروموزوم نقش ژن‌ها در طبیعت را بازی می‌کنند. یکی از ویژگی‌های اصلی الگوریتم‌های ژنتیک آن است که به طور متناوب بر روی فضای کدینگ و فضای جواب کار می‌کنند. اعمال ژنتیکی بر روی فضای کدینگ یا کروموزوم‌ها اِعمال می‌شود، در حالی که انتخاب و ارزیابی بر روی فضای جواب عمل می‌نماید.

در طبیعت نیز به همین شکل است یعنی افراد (کروموزوم‌ها) در یک فضای حقیقی غیر کد شده در حالت فنوتیپ حضور دارند. در صورت کد شدن با هر مکانیزمی حالت ژنوتیپ خود را بروز می‌دهند. ذکر این نکته ضروری است که هر زمان از کدینگ صحبت به میان می‌آید بطور پیش فرض منظور کد کردن از نوع باینری می‌باشد (رشته‌های دودویی). همچنین ساختمان داده مورد استفاده بطور پیش فرض، رشته می‌باشد.


2-7-1- کدینگ باینری
این تبدیل، تبدیل استاندارد در الگوریتم‌های ژنتیک می‌باشد. کد گذاری باینری ساده‌ترین کد گذاری و بهترین تبدیل برای عملگرهای ژنتیک است اما در مسائل پیچیده این نوع تبدیل چندان مناسب نیست چون معمولاً باعث می‌شود طول کروموزوم‌ها برای نگهداری اطلاعات پاسخ، بسیار بزرگ شود. در تبدیل باینری، اعضای جمعیت به رشته‌هایی از 0ها و 1ها تبدیل می‌شوند.

به عنوان مثال فرض کنید الگوریتم می‌خواهد ماکزیمم تابع F(x,y,z) را پیدا کند. در نظر بگیرید جستجو باید در اعداد صحیحِ مثبت و در محدوده 0 تا 255 انجام شود هر پاسخ ممکن شامل سه عدد X وY و Z می‌باشد.

طول هر عدد در محدوده مورد نظر مسأله در تبدیل  باینری حداکثر 8 بیت می‌باشد. اگر هر کروموزوم را به صورت XYZ در نظر بگیریم بنابراین برای پوشش دادن به تمام پاسخ‌های ممکن لازم است طول کروموزوم   بیت باشد. برای این مسأله کروموزوم C می‌تواند به شکل زیر باشد.
C=11010010  11100011 00110111

در همین مسأله اگر لازم باشد اعداد منفی نیز جستجو شود می‌توان یک بیت به ابتدای هر رشته اضافه کرد که مثلاً اگر 0 باشد، عدد، مثبت و اگر 1 باشد عدد، منفی در نظر گرفته شود.

000000001=1
100000001=-1

تبدیل اعداد اعشاری نیز می‌تواند با استفاده از چنین تمهیداتی انجام شود.
البته برای این نوع کدینگ دو روش در قسمت «نمایش رشته‌ها» به طور کامل بیان شده است.


2-7-2- کدینگ جایگشتی
در این روش، کروموزوم‌ها به صورت رشته‌ای از اعداد طبیعی نشان داده می‌شوند که هرکدام از این اعداد، مربوط به پارامتر ویژه‌ای در فضای حلّ مسأله است. ترتیب قرارگیری این اعداد مهم بوده و طول رشته دقیقاً با تعداد پارامترهای تعریف شده در مسأله برابر است. کاربرد این نوع کدگذاری در حل مسألۀ فروشندۀ دوره‌گرد است که تعریف آن در زیر آمده است.

در بسیاری از مسایل مانند مسأله «فروشنده دوره گرد» با جایگشت‌های مختلفی از مجموعه راه‌حل‌ها رو به رو هستیم. در این مسأله تعدادی شهر داریم که فاصله میان آنها معلوم است و با شروع از یک شهر و ختم به همان شهر می‌بایست:
1- از تمام شهرها فقط و فقط یکبار عبور نمائیم.
2- کمترین مسافت ممکنه را طی نماییم.

نکته‌ای که در اینجا مهم است و باعث شده تا کدینگ باینری روش مناسبی برای این مسأله نباشد، این نکته است که حتما باید برش میان دو والد به نحوی صورت بگیرد که هیچ عنصری تکراری وجود نداشته باشد.

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

شکل 2-2  ترکیب تک نقطه

البته در حالت جایگشتی می‌توان از PMX هم استفاده نمود.

شکل 2-3- ترکیب جایگشتی

برای جهش نیز از مکانیزم زیر استفاده می‌شود:
دو موقعیت کاملاً دلخواه انتخاب شده و جای آنها با یکدیگر تعویض می‌شود.

شکل 2-4 جهش - کدینگ جایگشتی 

2-7-3- کد گذاری مقدار
در این نوع روش کدگذاری، کروموزوم‌ها می‌توانند هر نوع داده مرتبط با مسأله را در رشتۀ خود اختیار نمایند. این داده‌ها می توانند از نوع اعداد حقیقی، عبارات منطقی، دستورات جهت‌یابی، داده‌های کد شده به صورت رشته‌های حرفی و... باشند. در این نوع کدگذاری تمامی مکانیزم‌های عملگر برش مانند حالت باینری، استفاده می‌شود. برای عملگر جهش نیز مانند زیر عمل می‌شود.

شکل 2-5- جهش: کدینگ مقدار

یعنی به بعضی ژن‌ها بطور تصادفی عددی اضافه شده یا از آنها کم می‌گردد.

[Zohreh Gholami]

2-7-4- کدینگ درخت
این روش که توسط «جان کوزا»  توسعه یافت، بیشتر برای برنامه‌نویسی ژنتیک  توسط نرم‌افزار «لیسپ»  مورد استفاده قرار می‌گیرد، که برنامه‌ها را به عنوان شاخه‌های داده در ساختار درخت نشان می‌دهد. در این روش تغییرات تصادفی می‌توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت، یا عوض کردن یک زیردرخت با دیگری به وجود آیند. یا به زبان ساده‌تر این طورمی‌توان گفت که: در این نوع کد گذاری یک درخت دودویی برای عبارت (کروموزوم) تشکیل می‌دهیم که معادل درخت پارس است و تمام اعمال مربوط به درخت پارس بر روی درخت قابل انجام است.

این روش بیشتر در نرم‌افزار کامپایلر فوق بکار برده می‌شود البته در نرم افزارهایی که تحت عنوان «کدهای الگوریتم ژنتیک» برای یک مسأله خاص نوشته می‌شوند از این نوع روش رمزگذاری و آدرس‌دهی کروموزوم استفاده می‌شود.

شکل 2-6 کدینگ درختی

برای جهش هم یک نود دلخواه تغییر می‌کند.



2-8- نمایش رشته‌ها
نمایش مناسب رشته‌ها به ویژگی‌های فضای جستجو بستگی دارد ولی معمولاً به صورت رشته‌های دودوئی نمایش داده می‌شوند. در حل با الگوریتم ژنتیک متغیرها عموماً به صورت دودوئی و با طول رشته ثابت کد گذاری می‌شوند. برای حلّ یک مسأله بهینه‌سازی به کمک الگوریتم ژنتیک ابتدا متغیرهای مسقل مسأله تشخیص داده می‌شود و سپس دامنۀ تغییرات معین می‌شود.


بنابر این که  هر متغیر پیوسته یا گسسته باشد یکی از روش‌های زیر را انتخاب می‌شود:
االف) متغیرهای پیوسته:
با فرض اینکه متغیر مورد نظر از   تا   در حال تغییر باشد و برای نشان دادن آن از یک رشته بیتی استفاده شده باشد.
ب) متغیرهای گسسته:
معمولاً در مسائلِ مربوط به طراحی استفاده از متغیرهای گسسته اجتناب‌ناپذیر است. برای مثال می‌توان از انتخاب جنس مواد و یا استفاده از جداول استاندارد نام برد. در هریک از موارد با فرض اینکه متغیر مورد نظر دارای n مقدار قابل قبول باشد. طول زیر رشته معادل آن از رابطه زیر به دست می‌آید.

برای مثال اگر متغیری دارای 8 مقدار باشد، برای تمام حالات به یک زیر رشته با سه خانه نیاز است. حال اگر متغیر مورد نظر دارای 10 مقدار متفاوت باشد به یک زیر رشته حداقل با 4 خانه نیاز است. ولی زیر رشته‌ای با 4 خانه توانایی 24 مقدار متفاوت را دارد. برای حل این مشکل می‌توان به تعداد مورد نظر (در اینجا 14 مورد) از مقادیری که در اختیار است به طور تصادفی انتخاب کرده و به صورت تکراری جایگزین کرد.

برای مثال فرض کنید در یک مسأله طراحی جنس قطعه مورد بررسی به عنوان متغیر بهینه‌سازی از میان جنس‌های آهن، چدن و برنج قابل انتخاب باشد برای بیان این متغیر   خواهد بود که به صورت زیر کد گذاری می‌شود:

آهن= 00         برنج= 01        چدن= 10    آهن=  11

همانگونه که نشان داده شده است برای فضای چهارم به صورت تصادفی یکی از سه جنس قابل قبول قرار داده شده است پس از اینکه تمام متغیر طراحی بصورت زیر دسته‌هایی در نظر گرفته شدند با کنار هم قرار دادن این زیر رشته‌ها به یک رشته دودوئی از اعداد به طول n خواهیم رسید. این رشته از اعداد که معرّف یک طرح خواهد بود همان کروموزوم است. فرمول ریاضی که برای محاسبه طول کروموزوم‌ها بکار می رود به شکل زیر می‌باشد:

رابطه 2-1 محاسبه طول کروموزوم

حال با داشتن مکان ابتدا و انتهای هر ژن می‌توان از روی کروموزوم مقدار هر ژن را محاسبه کرد. هر کروموزوم باید اطلاعاتی درباره راه‌حلی که نشان می‌دهد داشته باشد. یکی از روش‌های رمز گذاری که بیشتر مورد استفاده قرار می‌گیرد، رشته دوتایی است. نمونه‌ای از کروموزوم‌ها در این حالت، در شکل زیر نشان داده شده است.

شکل 2-7 نمونه کروموزوم الگوریتم ژنتیکی

هر کروموزوم به صورت رشته‌ای باینری نشان داده می‌شود. هر بخش موجود در رشته، ویژگی‌هایی از راه‌حل را نشان می‌دهد. احتمال دیگر آهن است که تمام رشته نمایان گر یک عدد باشد. البته راه‌های دیگر بسیاری برای رمز گذاری وجود دارد. رمز گذاری، عمدتاً به مسأله حل شده بستگی دارد. به طور مثال می‌توان مستقیماً اعداد صحیح و یا حقیقی را رمز گذاری کرد.

روش معمول برای رمز گشائی متغیرهای گسسته به این صورت است که جدولی از تمام حالات زیر رشته مربوط تشکیل می‌شود و هنگام رمز گشائی، معادل هر مقدار زیر رشته از جدول انتخاب می‌شود.


2-9- انواع روش‌های تشکیل رشته
برای تشکیل رشته دو روش وجود دارد:
الف) روش سری
در روش سری بیت‌های عددی متناظر هر واحد  مطابق شکل (2-8) کنار هم قرار می‌گیرند. لازم به توضیح  است که تا آخر برنامه هم محل هر واحد ثابت است و هیچ تغییری نمی‌کند، البته در ابتدای تشکیل رشته هیچ محدودیتی در انتخاب جایگاه وجود ندارد ولی بعد از تشکیل رشته تحت هیچ شرایطی نباید جابجا شوند.

شکل 2-8 روش سری

ب) روش محاطی
در روش محاطی بیت‌های عددی متناظر واحدها مطابق شکل (2-9) طوری کنار هم قرار می‌گیرند که در NP (تعداد واحدها) بیتی در کنار هم قرار می‌گیرند و هر بیت متعلق به یک واحد می‌باشد. به بیان ساده‌تر اینکه، جایگاه‌های بیتی در هر NP بیت به طور متناوب متعلق به یک واحد خاص می‌باشد.

شکل 2-9 روش محاطی

[Zohreh Gholami]

2-10- باز گرداندن رشته‌ها به مجموعه متغيرها
در روند اجراي الگوريتم ‍‍ژنتيك لازم است رشته‌ها به متغييرها تبديل شوند و به عبارت ديگر نمادهاي مربوط به هر رشته (نماد ژني) به دست آيند، تا از آنجا با قرار دادن متغيرها در تابع هدف، مقدار تابع هدف و در نتيجه ارزيابي آن رشته به دست آيد. بنابراين يكي از قسمت‌هاي مهمّ الگوريتم ژنتيك قسمت رمز گشايي است كه در مرحلۀ ارزيابي انجام مي‌شود.

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

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

ابتدا زيررشته مربوط به اين متغير مشخص مي‌شود. سپس مقدار واقعي آن در مبناي 10 به دست مي‌آيد. اكنون براي به دست آوردن مقدار متغير X با توجه داشته باشيم كه صورتي كه تعداد بيت مربوط به اين متغير برابر n باشد، در واقع ما متغير X را در يك فاصله  نگاشت كرده‌ايم كه عدد به دست آمده در مبناي 10 در واقع عدد مربوط به اين فاصله مي‌باشد. حال مقدار متغير X با توجه به رابطه (2-2) محاسبه مي‌شود.

رابطه 2-2 بازگرداندن رشته‌های  متناظر به مجموعۀ متغیرها

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


2-10-1- تعداد بيت‌هاي متناظر با هر متغير
تعداد بيت‌هاي متناظر با هر متغير در صورتي كه از رشته‌هاي بيتي استفاده شود، به صورت زير به دست مي‌آيد.

رابطه 2-3 محاسبه تعداد بيت‌هاي متناظر با هر متغير

كه در رابطه فوق X _max بیشترین مقدار مجاز متغير و X _min كمترين مقدار مجاز متغير X است و d نيز دقت مورد نظر براي اين متغير مي‌باشد. اكنون با استفاده از رابطه (2-4) مقدار n محاسبه مي‌كنيم. اگر در محاسبه مقدار n اعشاري شود، كوچكترين عدد صحيح بزرگتر يا مساوي آن را در نظر مي‌گيريم.

رابطه 2-4 محاسبه مقدار n برای استفاده در رابطه 2-3

همانطور كه گفته شد، تعداد بيت مورد نياز براي تك‌تك متغيرهاي مسأله به دست مي‌آيد و در نهايت در صورتي كه k متغير داشته باشيم طول هر رشته برابر خواهد بود با:

Ns= N1 + N2 + ... + Nk

رابطه 2-5- محاسبه طول رشته برای k متغیر

2-11- جمعيت
مفهوم جمعيت در الگوريتم ‍ژنتیک شبيه به چيزي است كه در زندگي طبيعي وجود دارد. براي مسأله گزاره‌هايي وجود دارند كه مي‌توانند به عنوان پاسخ، چه درست، چه غلط در نظر گرفته شوند. به اين گزاره‌ها پاسخ‌هاي ممكن يا شدني مي‌گوييم. مثلاً اگر مسأله يافتن ماكزيمم يك تابع در مجموعه اعداد صحيح باشد، تمام اعداد صحيح مي‌توانند به عنوان پاسخ شدني مسأله در نظر گرفته شوند.

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

در واقع تعداد اعضا پارامتري است كه با تغيير آن مي‌توان دقت جواب‌ها و سرعت همگرايي جستجو را بهبود بخشيد. در برخي مسائل يك جمعيت 8 عضوي كاملاً مناسب است در حالي كه در برخي يك جمعيت 100 عضوي نيز كافي نيست. براساس تجربه بهتر است تعداد اعضاي جمعيت عددي بين 10 تا 160 باشد.


2-11-1- ايجاد جمعيت اوليه
پس از تعيين سيستم كدينگ و مشخص شدن روش تبديل هر جواب به كروموزوم، بايد جمعيت اوليه‌ای از كروموزوم‌ها توليد نمود. در اكثر موارد، جمعيت اوليه به صورت تصادفي توليد مي‌شود. اما گاهي اوقات براي بالا بردن سرعت و كيفيت الگوريتم از روش‌هاي ابتكاري نيز براي توليد جمعيت اوليه استفاده مي‌گردد. در هر صورت عمومي‌ترين و راحت‌ترين روش، استفاده از يك رويكرد تصادفي مي‌باشد.

اندازۀ جمعيت اوليه معمولاً به سايز رشتۀ كد شده وابسته است. به عنوان مثال اگر كروموزوم‌ها دريك مسأله 32 بيتي هستند، قطعاً بايد جمعيت انتخابي اوليه بيشتر از حالتي باشد كه كروموزوم‌ها به عنوان مثال 16 بيتي هستند.

معمولاً احتمال برش بين 80 تا 95 درصد، احتمال جهش بين نيم تا 1 درصد و اندازه جمعيت بين 20 تا 30 در نظر گرفته مي‌شود. آنگاه به كروموزوم‌هاي انتخاب شده با توجه به يك تابع برازش، مقداري حقيقي كه نشان دهنده ارزش آنها است تخصيص داده مي‌شود و مراحل الگوريتم‌هاي ژنتيك ادامه مي‌يابد.


2-11-2- اندازه جمعيت
«گلدبرگ» براي محاسبه بهترين اندازه جمعيت براي كدهاي دودوئي متغيرهاي پيوسته تا طول حداكثر 60 رشته مقدار زير را پيشنهاد مي‌كند.

N Pop= 1.65*2(0.21*Lc

رابطه 2-6- محاسبه اندازه جمعیت

به طور مثال اگر طول هر کروموزوم برابر با 25 باشد، آنگاه داریم:

N Pop= 1.65*2(0.21*25)=62

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

N Pop= 1.65*2(0.21*35)=270

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

در صورتي كه تعداد اعضاي جمعيت بسيار زياد باشد، اگرچه وضعيت جستجو ممكن است به صورت بهتري نمايش داده شود زيرا با افزايش تعداد رشته‌ها، انتخاب رشتۀ بهتر امكان‌پذيرتر مي‌شود، ولي از طرفي نيازمندي‌هاي حافظه‌هاي كامپيوتر و زمان اجراي برنامه زياد مي‌شود. اگر تعداد اعضاي جمعيت نيز كوچكتر از حدّ مشخصي باشد، جمعيت مورد نظر فقط قسمت كوچكي از فضاي جستجو را نشان مي‌دهد و ممكن است جستجو براي رسيدن به حلّ بهينه در اين جمعيت موفقيت‌آميز نباشد يا مستلزم صرف زمان زيادي باشد، در عمل تعداد اعضاي جمعيت مقداري است كه به صورت تجربي به دست آمده و نشان داده شده است. با اين تعداد رشته در جمعيت، مي توان به حل‌هاي مناسبي دست يافت اين تعداد 2 الي 5/2 برابر طول هر رشته مي‌باشد.



2-12- محاسبه برازندگي (تابع ارزش)
تابع برازندگي از اِعمال تبديل مناسب بر روي تابع هدف يعني تابعي كه قرار است بهينه شود به دست مي‌آيد. اين تابع هر رشته را با يك مقدار عددي ارزيابي مي‌كند كه كيفيت آن را مشخص مي‌نمايد. هر چه كيفيت رشته جواب بالاتر باشد مقدار برازندگي جواب بيشتر است و احتمال مشاركت براي توليد نسل بعدي نيز افزايش خواهد يافت. بسته به اينكه مسأله مورد نظر بيشينه‌سازي يا كمينه‌سازي باشد برازندگيِ بيشتر مترادف با بيشينه يا كمينه بودن تابع هدف خواهد بود، از آنجايي كه الگوريتم ژنتيك طبيعتاً به دنبال بيشينه تابع است بايد مسائل كمينه‌سازي به بيشينه‌سازي تبديل شود.

چندين روش براي تبديل تابع هدف برازندگي وجود دارد. ساده‌ترين حالت مساوي قرار دادن تابع برازندگي با تابع هدف است. اين روش در مسائلي كه تابع هدف بايستي بيشينه شود مناسب است.

براي تبديل مسائل كمينه‌سازي به بيشينه‌سازي روش‌هاي مختلفي وجود دارد، با فرض اينكه مقدارِ   تابع هدف معادل فرد I ام باشد، ساده‌ترين راه، كم كردن   از يك مقدار ثابت C است بطوريكه به ازاي تمام نسل‌ها C>   باشد.

رابطه 2-7- تبدیل مسائل کمینه‌سازی به بیشینه‌سازی

در صورتي كه نتوانيم بزرگترين مقدار تابع هدف را حدس بزنيم مي‌توانيم در هر نسل   و   يافته و برازندگي را به صورت زير محاسبه ‌كنيم.

رابطه 2-8 تبدیل مسائل کمینه‌سازی به بیشینه‌سازی

روش ديگر، استفاده از تابع نمائي زير است:

رابطه 2-9 تبدیل مسائل کمینه‌سازی به بیشینه‌سازی

معمولاً مسائل بهينه‌سازي داراي قيدهايي هستند كه هنگام حل مسأله بايد ارضاء شوند در صورتيكه قيدها كم يا ساده باشند و احتمال ارضاء شدن آنها به خوديِ‌خود زياد باشد مي‌توان در هر نسل افرادي را كه قيدها را ارضاء نمي‌كنند با افراد جديد به طور تصادفي جايگزين كرد ولي در شرايط پيچيده قيدها به صورت تابع جريمه در تابع هدف منظور مي‌شوند.

رابطه 2-10 جایگزینی افراد جدید با افرادی که قیدهای مسأله را ارضاء نمی کنند

علامت و مقدار P_i  بايد به گونه‌اي باشد كه موجب شود افرادي از هر نسل كه كمتر قيدها را ارضاء مي‌كنند در نهايت از برازندگي كمتري بر خوردار باشند.



2-13- انواع روش‌های انتخاب
در مرحله انتخاب، يك جفت از كروموزوم‌ها برگزيده مي‌شوند تا با هم تركيب شوند، عملگر انتخاب رابط بين دو نسل است و بعضي از اعضاي نسل كنوني را به نسل آينده منتقل مي‌كند، بعد از انتخاب، عملگرهاي ژنتيك روي دو عضو برگزيده اعمال مي‌شوند، معيار در انتخاب اعضاء ارزش تطابق آنها مي‌باشد اما روند انتخاب حالتي تصادفي دارد.

شايد انتخاب مستقيم و ترتيبي به اين شكل كه بهترين اعضاء دو‌به‌دو انتخاب شوند در نگاه اول روش مناسبي به نظر برسد اما بايد به نكته‌اي توجه داشت؛ در الگوريتم ژنتيك ما با ژن‌ها روبه‌رو هستيم، يك عضو با تطابق پايين اگرچه در نسل خودش عضو مناسبي نمي‌باشد اما ممكن است شامل ژن‌هاي خوب باشد و اگر شانس انتخاب شدنش 0 باشد، اين ژن‌هاي خوب نمي‌توانند به نسل‌هاي بعد منتقل شوند. پس روش انتخاب بايد به گونه‌اي باشد كه به اين عضو نيز شانس انتخاب شدن داده شود. راه‌حل مناسب، طراحي روش انتخاب به گونه‌اي است كه احتمال انتخاب شدن اعضاي با تطابق بالاتر بيشتر باشد. انتخاب بايد به گونه‌اي صورت بگيرد كه تا جايي كه ممكن است هر نسل جديد نسبت به نسل قبلي‌اش تطابق ميانگين بهتري داشته باشد.

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


2-13-1- انتخاب چرخ رولت
انتخاب چرخ رولت كه اولين بار توسط «هولند» پيشنهاد شد يكي از مناسب‌ترين انتخاب‌هاي تصادفي بوده كه ايدۀ آن، احتمال انتخاب مي‌باشد. احتمال انتخاب متناظر با هر كروموزوم، براساس برازندگيِ آن محاسبه شده كه اگر   مقدار برازندگي كروموزوم k ام باشد، احتمال بقاي متناظر با آن كروموزوم عبارت است از:

رابطه 2-11 احتمال انتخاب در روش چرخ رولت

حال كروموزوم‌ها را براساس  مرتب كرده و  كه همان مقادير تجمعي  مي باشد که به صورت زير به دست مي‌آيد:

رابطه 2-12 محاسبه مقادیر تجمعی در چرخ رولت

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

شکل 2-10 چرخ رولت

انتخاب چرخ رولت، روشي است كه نسبت مقدار تطابق، اعضاء را انتخاب مي‌كند. اين روش يك چرخ رولت را شبيه‌سازي مي‌كند تا تعيين كند كدام اعضاء شانس باز توليد را دارند.

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

M تعداد عناصر بردار است اگر تعداد اعضاي مجموعه N باشد، هر عضو i 1,...N داراي تطابقي مانند  مي‌باشد. هر عضو i به نسبت ،   بار در v تكرار مي‌شود. هر چه  بيشتر باشد، عضو مكان‌هاي بيشتري را به خود اختصاص مي‌د‌هد. عدد از تشكيل بردار v يك مقدار تصادفي   انتخاب مي‌شود. اين مقدار به مكاني در بردار اشاره مي‌كند كه آن مكان خود معرّف عضوي از اعضاي جمعيت است، به عنوان مثال اگر جمعيتي با N=4 داشته باشيم و تطابق اعضا عبارت باشد از:

مقدار مجموع تطابق‌ها عبارت است از:

بردار v را برداري با 60 عنصر در نظر مي‌گيريم. اين بردار به صورت زير پر مي‌شود. به عضو 1، 10 مكان، به عضو 2، 10 مكان، به عضو 3، 15مکان و به عضو 4، 25 مكان اختصاص مي‌يابد.

حالا r بين 1 تا 60 به تصادف انتخاب مي‌شود. فرض كنيد r=32 نتيجه مي‌شود:

پس عضو 3 انتخاب مي شود.


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

در این روش، فقط تعداد اندکی از اعضای جمعیت کنونی، با اعضای جدید جایگزین می‌شوند، به عبارت دیگر، بدترین اعضا با فرزندانی که از بهترین اعضا بوجود آمده‌اند تعویض می‌شوند اما بافت کلّی جمعیت، چندان تغییر نمی‌کند.


2-13-3- انتخاب نخبه گرایی
ایدۀ نخبه‌سالاری یا گرایی، ویژگی تازه‌ای به پروسۀ انتخاب اضافه می‌کند، در نخبه سالاری، بهترین عضو هر جمعیت، زنده می‌ماند و در جمعیت بعد حضور دارد، به عبارت دیگر عضوی که بالاترین تطابق را دارد به طور خودکار به جمعیت جدید منتقل می‌شود. این روش ابتدا در سال 1975 توسط «کندی جونز» معرفی شد. اعمال نخبه سالاری در الگوریتم ژنتیک، معمولاً باعث بهبود کارایی آن می‌شود.


2-13-4- انتخاب رقابتی
این روش تعدادی از اعضای جمعیت را به تصادف انتخاب می‌کند و سپس اگر شرطی خاص برقرار باشد، بهترین یا تعدادی از بهترین‌های آنها را به عنوان والد بر می‌گزیند، اگر شرط برقرار نشود، بدترین عضو یا تعدای از بدترین‌ها، در تشکیل جمعیت آینده به عنوان والد در نظر گرفته می‌شوند.

شکل استاندارد این روش، رقابت دوتایی یا باینری است و به شکل زیر می‌باشد:
1- 2عضو به تصادف انتخاب می‌شوند.
2- مقدار r بین 0 و 1 به تصادف تعین می‌شود.
3- پارامتر توسط کاربر تعیین می‌شود. مثلاً 0.75=K
4- اگر r<k عضو برتر و اگر r≤K عضو بدتر بین این دو عضو، به عنوان والد انتخاب می‌شود.
5- دو عضو انتخاب شده برای رقابت، به جمعیت بر می‌گردند و می‌توانند دوباره در رقابت شرکت کنند.
روش انتخاب رقابتی می‌تواند به صورت رقابت n تایی نیز انجام شود.


2-13-5- انتخاب قطع سر
در این روش که توسط «گلدنبرگ» معرفی و ارائه شده، ابتدا یک عدد T که کوچکتر از صد می‌باشد، تعریف شده سپس کروموزوم‌ها را بر مبنای مقادیر برازندگی مرتب کرده و Tدرصدِ برتر را انتخاب می‌کنیم. حال از هر یک از آنها  T/100 کپی به نسل بعد انتقال می‌دهیم مثلاً فرض کنید T=20 و تعداد کروموزوم‌ها نیز 20 عدد باشد، بنابراین 20% کروموزوم‌های اول یعنی  4 = 100/5 تای اول را از لیست مرتب شده انتخاب کرده و از هر کدام 5 کپی در نظر می‌گیریم.


2-13-6- انتخاب قطعی بریندل
این روش که توسط «بریندل» معرفی و ارائه شده، به این صورت است که احتمال انتخاب برای هر کروموزوم طبق فرمول زیر محاسبه می‌شود:

رابطه 2-13 احتمال انتخاب در روش «قطعی بریندل»

و تعداد مورد انتظار برای هر کروموزوم نیز از رابطه به دست می‌آید.

رابطه 2-14 محاسبه مقادیر تجمعی در روش «قطعی بریندل»

حال هر کروموزوم بر طبق قسمت صحیح مقدار انتظار، به نمونه تخصیص داده می‌شود و سپس جمعیت بر حسب قسمت اعشار تعداد مورد انتظار، مرتب شده و به تعداد مورد نیاز جهت تکمیل جمعیت، به ترتیب از بالای لیست برداشته می‌شود.


2-13-7- انتخاب جایگزینی نسلی اصلاح شده
در این روش که توسط «وایتلی»  ارائه شده، ابتدا کروموزوم‌ها براساس مقدار برازش منظم شده، سپس به تعداد نوزادان تولید شده از انتهای لیست کروموزوم‌ها حذف می‌گردند، آنگاه نوزادان جایگزین کروموزوم‌های حذف شده می‌شوند. مثلاً اگر 10 کروموزوم وجود داشته باشد، ابتدا آنها را مرتب کرده و بعد اگر قرار باشد 4 نوزاد نیز تولید شود پس از تولید نوزادان، آنها جایگزین 4 کروموزوم آخر لیست می‌شوند.


2-13-8- انتخاب مسابقه
در این روش که توسط «گلدبرگ» ارائه شده، به تعداد Pop-Siz  ، مجموعه شامل چند عضو که از قبل مشخص شده، تولید کرده و در هر مجموعه بهترین عضو انتخاب می‌گردد. اندازه مجموعه فوق که به آن اندازه مسابقه گفته می‌شود معمولاً برابر 2 فرض می‌گردد.


2-13-9- انتخاب مسابقه تصادفی
این روش که توسط «وزل» ارائه شده، مانند حالت قبل بوده، با این تفاوت که به جای این که مجموعه به صورت تصادفی انتخاب شود با کمک چرخ رولت انتخاب شده و بهترین آن به عنوان یک عضو از نسل جدید در نظر گرفته می‌شود.



2-14- انواع روش‌های ترکیب
در طبیعت بقای نسل یکی از مهمترین فاکتورهاست و تنها عملگر ممکن برای این امر آمیزش است. در الگوریتم‌های ژنتیکی نیز آمیزش وجود دارد. آمیزش با تعویض ژن‌ها، بین دو کروموزوم انجام می‌گردد و هر کدام از کروموزوم‌ها خصوصیاتی از خود را به فرزندان انتقال می‌دهند. بدیهی است کروموزوم‌هایی که دارای برازندگی بیشتری هستند شانس بیشتری برای آمیزش دارند.

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

جفت‌هایی که در قسمت انتخاب، به عنوان والد در نظر گرفته شدند، در این قسمت ژن‌هایشان را با هم مبادله می‌کنند و اعضایی جدید بوجود می‌آورند.

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


2-14-1- جابه‌جایی دودوئی
روش‌های معمول جابجایی تک نقطه ، دو نقطه  و جابجایی یکنواخت  می‌باشد. ساده‌ترین جابجا کردن، جابجایی تک نقطه‌ای است. در جابجایی تک نقطه‌ای، ابتدا جفت کروموزوم والد (رشته دودوئی) در نقطه مناسبی در طول رشته بریده شده و سپس قسمت‌هایی از نقطه برش، با هم عوض می‌شوند، بدین ترتیب دو کروموزوم جدید به دست می‌آید که هر نقطه از آن ژن‌هایی را از کروموزوم‌های الد به ارث می‌برند.

برای جابجایی چند نقطه‌ای، m موقعیت جابجا شدن،   که   نقطه جابجایی و   طول کروموزوم می‌باشد را به صورت تصادفی و بدون تکرار انتخاب می‌کنیم، سپس جهت ایجاد فرزندی جدید بیت‌های بین نقاط مشخص شده در والدین با هم عوض می‌شوند. این عملیات در شکل (2-11) نشان داده شده است. فلسفه انجام جابجایی این است که قسمت‌هایی از کروموزوم که بیان کننده سهم بسزایی در عملکرد بهتر یک عضو خاص هستند ممکن است در زیر رشته‌های همسایه یافت نشوند.

شکل 2-11 جابجایی چند نقطه

به نظر می‌رسد نحوه عملکرد جابجایی در چند نقطه نسبت به روش همگرایی به مقادیر بالاتر برازندگی به پیشرفت و توسعه جستجو در فضای داده‌های مربوطه بیشتر کمک می‌کند، لذا جستجو در دامنه جواب قوی‌تر می‌شود. «یانگ» عملکرد جابجایی چند نقطه را مورد بررسی قرار داده و ثابت کرد که عملگرجابه جایی بیشتر، عملکرد الگوریتم ژنتیک را کاهش می‌دهد.

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

دو كروموزوم اوليه (والدين) و الگوي عملگر جابه‌جایي و فرزندان حاصل را در نظر بگيريد.
در اينجا مشاهده مي‌شود كه فرزند اول  O₁ بدين صورت ايجاد شده است كه اگر بيت مربوط در الگوي جابه‌جایي  Mask  یک باشد آن بيت در  O₁ برابر با مقدار بيت متناظر در  P₂ و همچنين اگر بيت مربوط در الگوي جابه‌جایي 0 باشد مقدار آن بيت در O₁ برابر با مقدار بيت متناظر در   است. رشته  O₁ با جابجا كردن  P₁ و  P₂ و در نظر گرفتن همين شيوه ايجاد شده است يعني مقدار 1 در رشته  Mask به معني مقدار بيت متناظر در  P₂ براي همان بيت در  O₂ است.

مشخصاً عملگر جابه‌جایي يكنواخت همانند عملگر جابه‌جائي چند نقطه‌اي باعث كاهش خطاي همگرايي ناشي از طول باينري استفاده شده و نوع كد كردن سري پارامترهاي داده شده مي‌شود. اين مسأله كمك مي‌كند كه بر خطاي همگرايي موجود در حالت جابه‌جایي تك نقطه‌اي در زيررشته‌هاي كوتاه غلبه كنيم بدون آنكه نياز به دانستن مقادير بيت‌هاي اعضا در كروموزوم‌هاي ارائه شده داشته باشيم.

«اسپرز»  و «دیجانگ»  نشان داده‌اند كه چگونه جابه‌جایي يكنواخت به وسيله احتمال عوض شدن و جابجا شدن بيت‌ها پارامتري مي‌شود. اين پارامتر فوق‌العاده مي‌تواند بدون توصيف يك همگرايي مربوط به طول رشته‌هاي استفاده شده در كنترل مقدار تغيير يافته در طول تركيب‌بندي مجدد استفاده شود هنگامي كه از عملگر جابه‌جایي يكنواخت در مقادير حقيقي استفاده شود به آن «تركيب‌بندي منفصل» گفته مي‌شود.

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

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

عملگر ديگري نيز عمل جابه‌جایي را مقيّد مي‌كند كه هميشه اعضاي جديدي ايجا كند در هر جايي كه ممكن باشد. معمولاً اين عملگر بدين صورت عمل مي‌كند كه مكان نقاط قطع را محدود مي‌كند به گونه‌اي كه نقاط قطع تنها جايي اتفاق مي‌افتد كه مقادير ژن در دو كروموزوم متفاوت است.