جستاری برالگوریتم ژنتیک‌

کاوش در آفرینش‌

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

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

جستجوی دیجیتال‌

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

تاکنون روش‌های بسیاری توسط طراحان الگوریتم‌ها برای انجام جستجو بر داده‌های دیجتالی ارایه شده است.
روش‌هایی به‌نام جستجوی سریع1 و جستجوی دودویی2، از ساده‌ترین الگوریتم‌هایی هستند که دانشجویان گرایش‌های مهندسی کامپیوتر در نخستین سال‌های دوره کارشناسی فرامی‌گیرند، اما این الگوریتم‌های ساده، هنگامی که با حجمی گسترده از داده‌ها روبرو شوند، کارایی ندارند و حتی الگوریتم‌های پیشرفته‌‌تر، مانند جستجوی سخت‌سازی شبیه‌سازی‌شده3 و الگوریتم عمیق‌شونده تکراری4 نیز در هنگام رویارویی با مسایل ابرفضا5 از یافتن راه‌حل یا ناحیه دلخواه درمی‌مانند. در این میان، یک روش جادویی وجود دارد که مسایل بزرگ را به‌سادگی و به‌گونه‌ای شگفت‌انگیز حل می‌کند و آن الگوریتم ژنتیک6 است.

نظریه تکامل طبیعی‌

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

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

قانون جنگل‌

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

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

الگوریتم ژنتیک‌

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

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

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

پس از انتخاب برخی از اعضا (که احتمال گزینش آنها بر پایه تابع برازندگی تصادفی است) آنها در تولید نسل آینده مشارکت می‌کنند. کروموزوم فرزندان ترکیبی از ساختار ژنی والدین است. چگونگی انتخاب هر یک از ژن‌های والدین و ترکیب آنها برای ساختن ژن فرزندان معمولا توسط یک تابع تصادفی انجام می‌شود. از این رو هر فرزند تا اندازه‌ایx)  درصدx: عددی تصادفی است) شبیه والد یکم و تا حدودی00-x) 1درصد) شبیه والد دوم خواهد بود.

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

در شماره آینده، الگوریتم زنتیک را با نمایش چند مثال کاربردی ادامه خواهیم داد.

پانوشت‌ها:
 Quick Search .1
 Binary Search. 2
 Simulated Annealing.3
 Iterative Deepening .4
 Hyper Space.5
 Genetic Algorithm (GA).6
s. Darwin”. Evolutionary Theory.7
Mutation. 8
9. واژه ژن در زبان‌های اروپایی، برگرفته از واژه اوستایی «ژن »jan/، به‌معنای زاینده است و واژه` «زن» و مصدر «زایش»  و «زندگی» در فارسی امروزی نیز از همان ریشه است. در گویش کردی هنوز «زن» به‌همان صورت باستانی «ژن» خوانده می‌شود.
Population.10
 Objects.11
Fitness Function.12
Evaluation Function.13
Reproduction.14

برای دریافت اطلاعات بیشتر ر.ک. به:

 Stuart J. Russell And PeterNorvig, -
Artificial Intelligence:A Modern Approach,
.1994 Prentice-Hall International Inc,
 Steven L. Tanimoto, The Elements of-
 Artificial  Intelligence Using Common Lisp,
  .1995 nd Edition,2Computer Science Press, 
Mitchel T. M., Machine Learning,
.1997 McGraw-Hill,-
 http://en.wikipedia.org/-
wiki/Search-algorithm

امیرشهاب شاهمیری‌