کاربر:FundamentalGeneticAlgorithm

مفاهیم بنیادین در علم ژنتیک

به طور کلی الگوریتم ژنتیک از یک سری مفاهیم پایه و کلی تشکیل شده است که عبارتند از :

• phenotype
• genotype
• gene
• chromosome
• population
• crossover
• mutation
• selection method
• fitness function

که هر کدام از این مفاهیم توضیح داده می شود.

phenotype

این پارامتر در بیولوژی و در زیست شناسی، ساختار کلی اعضای موجود زنده را مشخص می کند.به عنوان مثال می توان به هر کدام از اعضای بدن انسان اشاره کرد.

genotype

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

gene

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

chromosome

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

population

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

crossover

دو پارامترمهم عبارتند از پارامترهای crossover و mutation.پارامتر crossover انواع مختلفی دارد.یکی از مهمترین آنها one point crossover نام دارد.به این معنی که برای هر کروموزومی که به عنوان parent ایجاد شده است یک برش به صورت تصادفی ایجاد می گرددو فرزند جدید شامل قسمت ابتدایی کروموزوم از parent اول و قسمت انتهایی از parent دوم را در بر می گیرد. نوع دیگری از crossover را می توان uniform crossover را نام برد. به این معنی که فرزندی که ایجاد می شود به صورت کاملأ تصادفی یا از کروموزوم های parent اول و یا از کروموزوم های parent دوم ایجاد می شود.

mutation

جهشی که به صورت تصادفی ایجاد شد و در نتیجه فرزند جدید به وجود می آید. مثلأ در علوم کامپیوتر ممکن است یک رقم صفر یا یک رقم یک باینری جابجا شود.

selection method

متدی است که برای اینکه تابع شایستگی انجام شود، مورد استفاده قرار می گیرد. به عنوان مثال اگر از روش Tournament استفاده شود به این معنی است که پس از چند بار مسابقه، آن کروموزوم هایی که مقدار تابع شایستگی بیشتری دارند، به عنوان فرزند برای نسل بعدی انتخاب می شود. به عنوان مثال در علوم کامپیوتر، اگر چندین بار رشته های اعداد باینری به صورت جدا از هم به عنوان چندین parents ایجاد شده با شند، یک معیار سنجش بهینگی برای انتخاب بعدی برای هر یک از رشته های ایجاد شده وجود دارد به نام تابع شایستگی. هر کدام از رشته های ایجادشده که مقدار این تابع مقدار بیشتری داشته باشد، برای نسل بعدی انتخاب می شود.

fitness function

بر پایه متد انتخابی، مقدار آن معین می شود.

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

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

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

phenotype

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

بازنمایی یک نمونه زمان بندی شامل 10 وظیفه بر روی 10 ماشین

genotype

معادل بازنمایی کار مورد نظر در فضای مدل سازی بصورت ژنتیک گفته می شود. براي اینکار ابتدا نیاز داریم شکل مناسب بازنمایی مساله را بصورت یک کروموزوم ارائه نماییم. اگر مجموعه کارها را بصورت مجموعه J فرض کنیم:

J = {0,1,2,...}

و هر کار j از این مجموعه شامل Nj فعالیت باشد، بنابراین یک نمونه کروموزوم براي حالت J=2 و N0=N1=3 را میتوان بصورت زیر نمایش داد، که در آن هر بار تکرار شماره j در کروموزوم نشان دهنده انجام یکی از فعالیت هاي آن کار به ترتیب مشخص شده در Nj می باشد. مثلا k امین تکرار کار j نشان دهنده انجام k امین فعالیت j است.

[0, 0, 1, 1, 0, 1]

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

gene

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

chromosome

معادل انواع مختلف زمان بندی است. هر چیدمانی که صفرها و یک ها در کنار یکدیگر ایجاد می کنند به معنی نوع خاصی از زمان بندی که معادل کروموزوم در علم ژنتیک است. ما به تعداد (تعداد فعالیت ها*کار) نوع زمان بندی داریم.

population

در بحث زمان بندی، برابر است با تعداد حالاتی که می توانند کارها و فعالیت ها در کنار یکدیگر قرار بگیرند. یا به عبارت دیگر برابر است با (job*Nj)

crossover

بر مبنای نوع خاصی از انواع crossover که وجود دارد که ما آن را معین می کنیم، باعث به وجود آمدن زمان بندی خاصی می شود. معادل چیدمان خاصی است که زمان بندی خاصی را به وجود می آورد.

mutation

جهشی که بر روی کروموزوم ایجاد می شود باعث می شود که ترتیب انجام فعالیت ها عوض شده و در نهایت منجر به زمان بندی خاصی می شود.