فهرست مطالب :

فصل اول

۱-۱- مقدمه

۱-۲- به دنبال تکامل…

۱-۳- ایدۀ اصلی استفاده از الگوریتم ژنتیک

۱-۴- درباره علم ژنتیک

۱-۵- تاریخچۀ علم ژنتیک

۱-۶- تکامل طبیعی (قانون انتخاب طبیعی داروین)

۱-۷- رابطه تکامل طبیعی با روش‌های هوش مصنوعی

۱-۸- الگوریتم

۱-۸-۱- الگوریتم‌های جستجوی ناآگاهانه

۱-۸-۱-الف- جستجوی لیست

۱-۸-۱-ب- جستجوی درختی

۱-۸-۱-پ- جستجوی گراف

۱-۸-۲- الگوریتم‌های جستجوی آگاهانه

۱-۸-۲-الف- جستجوی خصمانه

۱-۹- مسائل NP-Hard

۱-۱۰- هیوریستیک

۱-۱۰-۱- انواع الگوریتم‌های هیوریستیک

فصل دوم

۲-۱- مقدمه

۲-۲- الگوریتم ژنتیک

۲-۳- مکانیزم الگوریتم ژنتیک

۲-۴- عملگرهای الگوریتم ژنتیک

۲-۴-۱- کدگذاری

۲-۴-۲- ارزیابی

۲-۴-۳- ترکیب

۲-۴-۴- جهش

۲-۴-۵- رمزگشایی

۲-۵- چارت الگوریتم به همراه شبه کد آن

۲-۵-۱- شبه کد و توضیح آن

۲-۵-۲- چارت الگوریتم ژنتیک

۲-۶- تابع هدف

۲-۷- روش‌های کد کردن

۲-۷-۱- کدینگ باینری

۲-۷-۲- کدینگ جایگشتی

۲-۷-۳- کد گذاری مقدار

۲-۷-۴- کدینگ درخت

۲-۸- نمایش رشته‌ها

۲-۹- انواع روش‌های تشکیل رشته

۲-۱۰- باز گرداندن رشته‌ها به مجموعه متغیرها

۲-۱۰-۱- تعداد بیت‌های متناظر با هر متغیر

۲-۱۱- جمعیت

۲-۱۱-۱- ایجادجمعیت اولیه

۲-۱۱-۲- اندازه جمعیت

۲-۱۲- محاسبه برازندگی (تابع ارزش)

۲-۱۳- انواع روش‌های انتخاب

۲-۱۳-۱- انتخاب چرخ رولت

۲-۱۳-۲- انتخاب حالت پایدار

۲-۱۳-۳- انتخاب نخبه گرایی

۲-۱۳-۴- انتخاب رقابتی

۲-۱۳-۵- انتخاب قطع سر

۲-۱۳-۶- انتخاب قطعی بریندل

۲-۱۳-۷- انتخاب جایگزینی نسلی اصلاح شده

۲-۱۳-۸- انتخاب مسابقه

۲-۱۳-۹- انتخاب مسابقه تصادفی

۲-۱۴- انواع روش‌های ترکیب

۲-۱۴-۱- جابه‌جایی دودوئی

۲-۱۴-۲- جابه‌جایی حقیقی

۲-۱۴-۳- ترکیب تک‌نقطه‌ای

۲-۱۴-۴- ترکیب دو نقطه‌ای

۲-۱۴-۵- ترکیب n نقطه‌ای

۲-۱۴-۶- ترکیب یکنواخت

۲-۱۴-۷- ترکیب حسابی

۲-۱۴-۸- ترتیب

۲-۱۴-۹- چرخه

۲-۱۴-۱۰- محدّب

۲-۱۴-۱۱- بخش_نگاشته

۲-۱۵- احتمال ترکیب

۲-۱۶- تحلیل مکانیزم جابجایی

۲-۱۷- جهش

۲-۱۷-۱- جهش باینری

۲-۱۷-۲- جهش حقیقی

۲-۱۷-۳- وارونه سازی بیت

۲-۱۷-۴- تغییر ترتیب قرارگیری

۲-۱۷-۵- وارون سازی

۲-۱۷-۶- تغییر مقدار

۲-۱۸- محک اختتام اجرای الگوریتم ژنتیک

۲-۱۹- انواع الگوریتم‌های ژنتیکی

۲-۱۹-۱- الگوریتم ژنتیکی سری

۲-۱۹-۲- الگوریتم ژنتیکی موازی

۲-۲۰- مقایسه الگوریتم ژنتیک با سیستم‌های طبیعی

۲-۲۱- نقاط قوّت الگوریتم‌های ژنتیک

۲-۲۲- محدودیت‌های GAها

۲-۲۳- استراتژی برخورد با محدودیت‌ها

۲-۲۳-۱- استراتژی اصلاح عملگرهای ژنتیک

۲-۲۳-۲- استراتژی رَدّی

۲-۲۳-۳- استراتژی اصلاحی

۲-۲۳-۴- استراتژی جریمه‌ای

۲-۲۴- بهبود الگوریتم ژنتیک

۲-۲۵- چند نمونه از کاربردهای الگوریتم‌های ژنتیک

فصل سوم

۳-۱- مقدمه

۳-۲- حلّ معمای هشت وزیر

۳-۲-۱- جمعیت آغازین

۳-۲-۲- تابع برازندگی

۳-۲-۳- آمیزش

۳-۲-۴- جهش ژنتیکی

۳-۳- الگوریتم ژنتیک و حلّ مسألۀ فروشندۀ دوره‌گرد

۳-۳-۱- حل مسأله TSP به وسیله الگوریتم ژنتیک

۳-۳-۲- مقایسه روشهای مختلف الگوریتم و ژنتیک برای TSP

۳-۳-۳- نتیجه گیری

۳-۴- حلّ مسأله معمای سودوکو

۳-۴-۱- حل مسأله

۳-۴-۲- تعیین کروموزم

۳-۴-۳- ساختن جمعیت آغازین یا نسل اول

۳-۴-۴- ساختن تابع از ارزش

۳-۴-۵- ترکیب نمونه‌ها و ساختن جواب جدید

۳-۴-۶- ارزشیابی مجموعه جواب

۳-۴-۷- ساختن نسل بعد

۳-۵- مرتب سازی به کمک GA

۳-۵-۱- صورت مسأله

۳-۵-۲- جمعیت آغازین

۳-۵-۳- تابع برازندگی

۳-۵-۴- انتخاب

۳-۵-۵- ترکیب

۳-۵-۶- جهش

فهرست منابع و مراجع

پیوست

واژه‌نامه

چکیده :

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

واژگان کلیدی: الگوریتم ژنتیک، هیوریستیک، ترکیب و جهش، تکامل طبیعی داروین، معمای هشت وزیر, GA

۱-۱- مقدمه

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

۱-۲- به دنبال تکامل…
بسیاری از دانشمندان و اندیشمندان، میل به تکامل را مهترین عامل پیشرفت دستگاه آفرینش و انسان می‌دانند. از این دیدگاه هر پدیده‌ای را که بنگرید، یک مسأله جستجوست. انسان همواره می‌کوشد تا به تکامل برسد، از این رو می‌اندیشد، می‌پژوهد، می‌کاود، می‌سازد، می‌نگارد و همواره می‌کوشد تا باقی بماند. حتی می‌‌توان گفت که میل به زادن فرزند، گامی در برآوردن این نیاز و البته دیگر جانداران است. می‌توان این تلاش در راه رسیدن به تکامل را یک مسألۀ جستجو تعبیر کرد.
کوشش یک مؤسسه اقتصادی یا تولیدی –که تابعی برای تبدیل داده‌ها به ستادهاست- برای کمینه کردن هزینه‌ها و بیشینه کردن سود، یک مسألۀ جستجو است. تلاش یک سپاه در حال جنگ، برای وارد کرد بیشترین خسارات بر دشمن با از دست دادن کمترین نیرو و جنگ‌افزار، یا کوشش یک دانش‌آموز برای دست یافتن به بالاترین نمره، سعی یک موسیقیدان یا نگارگر برای خلق زیباترین اثر هنری، تلاش یک کاندیدا برای به دست آوردن بیشترین رأی، طراحی یک نجّار برای ساختن راحت‌ترین صندلی، تلاش و نقشه چینی ورزشکاران و مربّیان برای یافتن راه‌های پیروزی بر حریف و… همگی جستجویی در فضای یک مسأله برای یافتن نقاط یا ناحیه بهینگی (بیشینه یا کمینه) هستند و همین امر موجب پیشرفت تمدن و آفرینش شده است.
در دانش کامپیوتر و فناوری اطلاعات هم «جستجو» یکی از مهمترین مسائل است. تنها کافیست که حجم اطلاعات قرار گرفته بر حافظه‌های گوناگون و اینترنت را در نظر بگیریم تا جایگاه ویژه آن را دریابیم.
تاکنون روشهای بسیاری توسط طراحان الگوریتم‌ها برای انجام جستجو بر داده‌های دیجیتالی ارائه شده است. روش‌هایی به نام جستجوی سریع و جستجوی دودویی ، از ساده‌ترین الگوریتم‌هایی هستند که دانشجویان گرایش‌های مهندسی کامپیوتر در نخستین سال‌های دوره کارشناسی فرا می‌گیرند، امّا این الگوریتم‌ها شاید، هنگامی که با حجمی گسترده از داده‌ها روبرو شوند، کارایی ندارند و حتی الگوریتم‌های پیشرفته‌تر مانند جستجوی بازپخت شبیه‌سازی شده و الگوریتم عمیق‌شوندۀ‌ تکراری نیز در هنگام رویارویی با مسائل ابرفضا از یافتن راه‌حل یا ناحیه‌های دلخواه در می‌مانند. در این میان یک روش جادویی وجود وجود دارد که مسائل بزرگ را به سادگی و به گونه‌ای شگفت‌انگیز حل می‌کند و آن «الگوریتم ژنتیک» است. ناگفته پیداست که واژۀ «الگوریتم ژنتیک» از دو واژۀ «الگوریتم» و «ژنتیک» تشکیل شده است که خود مبیّن این مطلب است که این روش از دو علم ریاضی و زیست‌شناسی برای حل مسائل کمک می‌گیرد.
الگوریتم‌ژنتیک بر خلاف دیگر روش‌های جستجو، که توسط طراحان نگاشته می‌شوند، در حقیقت به دست دستگاه آفرینش پدید آمده، و پس از شناخت نسبی دانشمندان از این روش به صورت مسأله‌ای ریاضی فرموله شده و وارد دانش مهندسی کامپیوتر و دیگر علوم مرتبط گردیده است. در یکی دو دهه گذشته که این الگوریتم در علوم مهندسی بکار گرفته شده، ناباورانه چنان دست‌آوردها و نتایج شگفت‌انگیزی داشته که نگاه بسیاری از دانش‌پژوهان علوم گوناگون فنی‌مهندسی را به خود جلب کرده است.[۱]

۱-۳- ایدۀ اصلی استفاده از الگوریتم ژنتیک
در دهه ۷۰ میلادی دانشمندی از دانشگاه میشیگان به نام «جان هلند» ایده استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. (ژنها قطعاتی از یک کروموزوم هستند که اطلاعات مورد نیاز برای یک مولکول DNA یا یک پلی پپتید را دارند. علاوه بر ژنها، انواع مختلفی از توالی‌های مختلف تنظیمی در روی کروموزوم‌ها وجود دارد که در همانندسازی، رونویسی و… شرکت دارند.( . فرض کنید مجموعه خصوصیات انسان توسط کروموزوم‌های او به نسل بعدی منتقل می‌شوند. هر ژن در این کروموزوم‌ها نماینده یک خصوصیت است. بعنوان مثال ژن ۱ می‌تواند رنگ چشم باشد، ژن ۲ طول قد، ژن ۳ رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بَدیهیست که در عمل چنین اتفاقی رخ نمی‌دهد. در واقع بصورت همزمان دو اتفاق برای کروموزوم‌ها می‌افتد. اتّفاق اول موتاسیون(جهش) است. موتاسیون به این صورت است که بعضی ژن‌ها بصورت کاملاً تصادفی تغییر می‌کنند. البته تعداد اینگونه ژن‌ها بسیار کم می‌باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلاً ژن رنگ چشم می‌تواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد، در حالی که تمامی نسل قبل دارای چشم قهوه‌ای بوده‌اند. علاوه بر موتاسیون اتفاق دیگری که می‌افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به موتاسیون رخ می‌دهد چسبیدن ابتدای یک کروموزوم به انتهای یک کروموزوم دیگر است. این همان چیزیست که مثلاً باعث می‌شود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری می‌کند. [۱۰]
حال می‌توانیم اینگونه بیان کنیم که: الگوریتم ژنتیک ابزاری می‌باشد که توسط آن ماشین می‌تواند مکانیزم انتخاب طبیعی را شبیه سازی نماید. این عمل با جستجو در فضای مسأله جهت یافتن جواب برتر و نه الزاماً بهینه صورت می‌پذیرد.[۱۳] الگوریتم ژنتیک را می‌توان یک روش جستجوی کلّی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید می کند.[۳] در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند.[۱۰]

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

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

۱-۶- تکامل طبیعی (قانون انتخاب طبیعی داروین )
هنگامی که لغت تنازع بقا به کار می‌رود اغلب بار ارزشی منفی آن به ذهن می‌آید. شاید همزمان قانون جنگل به ذهن برسد و حکم بقای قوی‌ترها !
البته همیشه هم قوی‌ترین‌ها برنده نبوده‌اند. مثلاً دایناسورها با وجود جثّه عظیم و قوی‌تر بودن در طی روندی کاملاً طبیعی بازیِ بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف‌تر از آنها حیات خویش را ادامه دادند. ظاهراً طبیعت، بهترین‌ها را تنها بر اساس هیکل انتخاب نمی‌کند! در واقع درست‌تر آنست که بگوییم طبیعت مناسب‌ترین‌ها را انتخاب می‌کند نه بهترین‌ها.
قانون انتخاب طبیعی بدین صورت است که تنها گونه‌هایی از یک جمعیت ادامه نسل می‌دهند که بهترین خصوصیات را داشته باشند و آنهایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین می‌روند.[۱۰]
برای نمونه می‌توان گفت که: در میان یک گلّه گرگ با افرادِ دارای ژن‌های گوناگون، گرگی احتمال بقای بالاتر را دارد که قوی‌تر از دیگران است، چراکه هم امکان بیشتری برای جفت‌گیری و گسترش ژن خود را دارد و هم بیش از گرگ‌های ضعیف‌تر به شکار دست یافته، زنده می‌ماند. در یک گلّه گوزن نیز وضع به همین شکل است: گوزن ضعیف‌تر هم کمتر امکان تولید مثل می‌یابد و هم زودتر توسّط درندگان گرفتار می‌آید. [۱]
و یا در مثالی دیگر، فرض کنید گونۀ خاصی از افراد، هوش بیشتری از بقیه افرادِ یک جامعه دارند. در شرایط کاملاً طبیعی، این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتاً بالاتری خواهند داشت و این رفاه، خود باعث طول عمر بیشتر و باروری بهتر خواهد بود (توجه کنید شرایط، طبیعیست نه در یک جامعه سطح بالا با ملاحظات امروزی؛ یعنی طول عمر بیشتر در این جامعۀ نمونه با زاد و ولد بیشتر همراه است). حال اگر این خصوصیّت (هوش) ارثی باشد بالطّبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشترِ این‌گونه افراد، بیشتر خواهد بود. اگر همین روند را ادامه دهید خواهید دید که در طی نسل‌های متوالی دائماً جامعۀ نمونۀ ما باهوش و باهوش‌تر می‌شود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملاً افراد کم‌هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائماً در حال افزایش است.
بدین ترتیب می‌توان دید که طبیعت با بهره‌گیری از یک روش بسیار ساده (حذف تدریجی گونه‌های نامناسب و در عین حال تکثیر بالاتر گونه‌های بهینه)، توانسته است دائماً هر نسل را از لحاظ خصوصیّات مختلف ارتقاء بخشد.
البتّه آنچه در بالا ذکر شد به تنهایی توصیف کنندۀ آنچه واقعاً در قالب تکامل در طبیعت اتفاق می‌افتد نیست. بهینه‌سازی و تکامل تدریجی به خودی خود نمی‌تواند طبیعت را در دسترسی به بهترین نمونه‌ها یاری دهد. اجازه دهید تا این مسأله را با یک مثال شرح دهیم:
پس از اختراع اتومبیل به تدریج و در طیّ سال‌ها اتومبیل‌های بهتری با سرعت‌های بالاتر و قابلیت‌های بیشتر نسبت به نمونه‌های اولیه تولید شدند. طبیعیست که این نمونه‌های متأخّر حاصل تلاش مهندسانِ طرّاح جهت بهینه‌سازی طرّاحی‌های قبلی بوده‌اند. اما دقّت کنید که بهینه‌سازی یک اتومبیل، تنها یک «اتومبیل بهتر» را نتیجه می‌دهد.
اما آیا می‌توان گفت اختراع هواپیما نتیجه همین تلاش بوده است؟ یا فرضاً می‌توان گفت فضا‌پیماها حاصل بهینه‌سازی طرح اولیه هواپیماها بوده‌اند؟
پاسخ اینست که گرچه اختراع هواپیما قطعاً تحت تأثیر دستاورهای صنعت اتومبیل بوده است؛ اما به‌هیچ‌وجه نمی‌توان گفت که هواپیما صرفاً حاصل بهینه‌سازی اتومبیل و یا فضا‌پیما حاصل بهینه‌سازی هواپیماست. در طبیعت هم عیناً همین روند حکم‌فرماست. گونه‌های متکامل‌تری وجود دارند که نمی‌توان گفت صرفاً حاصل تکامل تدریجی گونه قبلی هستند.
در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مسأله یاری کند مفهومیست به نام تصادف یا جهش.
به عبارتی طرح هواپیما نسبت به طرح اتومبیل یک جهش بود و نه یک حرکت تدریجی. در طبیعت نیز به همینگونه ‌است. در هر نسل جدید بعضی از خصوصیات به صورتی کاملاً تصادفی تغییر می‌یابند سپس بر اثر تکامل تدریجی که پیشتر توضیح دادیم در صورتی که این خصوصیت تصادفی شرایط طبیعت را ارضاء کند حفظ می‌شود در غیر این‌صورت به شکل اتوماتیک از چرخه طبیعت حذف می‌گردد.
در واقع می‌توان تکامل طبیعی را به این‌صورت خلاصه کرد: جست‌وجوی کورکورانه (تصادف) + بقای قوی‌تر.[۱۰]

۱-۷- رابطه تکامل طبیعی با روش‌های هوش مصنوعی
حال ببینیم که رابطه تکامل طبیعی با روش‌های هوش مصنوعی چیست. هدف اصلی روش‌های هوشمندِ به کار گرفته شده در هوش مصنوعی، یافتن پاسخ بهینه مسائل مهندسی است. بعنوان مثال اینکه چگونه یک موتور را طراحی کنیم تا بهترین بازدهی را داشته باشد یا چگونه بازوهای یک ربات را متحرک کنیم تا کوتاه‌ترین مسیر را تا مقصد طی کند (دقت کنید که در صورت وجود مانع یافتن کوتاه‌ترین مسیر دیگر به سادگی کشیدن یک خط راست بین مبدأ و مقصد نیست) همگی مسائل بهینه‌سازی هستند.
روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی را بعنوان نقطه بهینه کلی در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مسأله خاصی کاربرد دارند. این دو نکته را با مثال‌های ساده‌ای روشن می‌کنیم.
به شکل زیر توجه کنید. این منحنی دارای دو نقطه ماکزیمم می‌باشد. که یکی از آنها تنها ماکزیمم محلی است. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک مقدار ماکزیمم تابع را بیابیم. مثلاً از نقطه ۱ شروع کنیم و تابع را ماکزیمم کنیم. بدیهی است اگر از نقطه ۱ شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از آن متوقف خواهد شد. اما در روش‌های هوشمند، به ویژه الگوریتم ژنتیک بدلیل خصلت تصادفی آنها حتی اگر هم از نقطه ۱ شروع کنیم باز ممکن است در میان راه نقطه A به صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی را خواهیم داشت.

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

۱-۸- الگوریتم
در علوم کامپیوتر و ریاضیات، یک الگوریتم جستجو، الگوریتمی است که یک مسأله را به عنوان ورودی می‌گیرد و بعد از ارزیابی کردن راه‌حل‌های ممکن، یک راه‌حل برای آن مسأله برمی‌گرداند. هنگامی که مسأله‌ای را حل می‌کنیم معمولاً دنبال آن هستیم که بهترین راه‌حل و یا به بیان دیگر به یک حلّ بهینه از بین حل‌های ممکن برای مسأله برسیم.[۹] به محدوده‌ای که جواب‌های مسأله قابل قبول می‌باشند به طوری که جواب بهینه هم یکی از زیرمجموعه‌های این محدوده است «فضای جستجو» نامیده می‌شود. هر نقطه از محدودۀ فضای جستجو نشان دهندۀ یکی از روش‌های حلّ مسأله می‌باشد.[۵] و یا به بیانی ساده‌تر می‌توان گفت: مجموعۀ راه‌حل‌های ممکن برای یک مسأله را فضای جستجو می‌نامند.
مهمترین عامل در حل هر مسأله، جستجو به دنبال پاسخ‌های احتمالی مسئله است. [۱۵]به طور کلّی با دو دسته از الگوریتم‌ها مواجه هستیم؛ بعضی از الگوریتم‌ها که با عنوان الگوریتم‌های ناآگاهانه شناخته می‌شوند الگوریتم‌هایی هستند که از روش‌های ساده‌ای برای جستجوی فضای نمونه استفاده می‌کنند. در حالی که الگوریتم‌های آگاهانه با استفاده روش‌هایی مبتنی بر دانش در بارۀ ساختار فضای جستجو، می‌کوشند تا زمان جستجو را کاهش دهند.
در کتاب «راسل» این الگوریتم‌ها به شکل زیر رده‌بندی شده‌اند:
• الگوریتم‌های ناآگاهانه
• الگوریتم‌های آگاهانه

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

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

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

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

۱-۸-۲- الگوریتم‌های جستجوی آگاهانه
در یک جستجوی آگاهانه، از نوع خاصی از مسائل به عنوان راهنما استفاده می‌شود. یک گونۀ خوب، یک جستجوی آگاهانه با کارایی قابل توجّهی نسبت به جستجوی ناآگاهانه به وجود می‌آورد. الگوریتم‌های برجستۀ کمی از جستجوی آگاهانۀ یک لیست وجود دارد. یکی از این الگوریتم‌ها Hash Table با یک تابع Hash که برمبنای نوع مسأله‌ای که دردست است می‌باشد. بیشتر الگوریتم‌های جستجوی آگاهانه، بسطی از درخت‌ها هستند. همانند الگوریتم‌های ناآگاهانه، این الگوریتم‌ها برای گراف‌ها نیز می‌توانند به کار روند.[۹]
دلیل نیاز به روش‌های جستجوی آگاهانه، نیاز به کاهش هزینۀ زمانی مورد نیاز برای حلّ مسأله است. در واقع به این دلیل که ما تمایل داریم مسائل را در زمان کمتری حل کرده و از بررسی تمام حالات ممکن اجتناب کنیم، می‌بایست روشی برای تشخیص کیفیت مسیر (حتی به شکل نسبی) داشته باشیم.[۱۵]

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

فایل کامل این تحقیق ۱۵۷ صفحه بصورت ورد WORD می باشد.
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه