نمایش ژنوتیپ Genotype

نمایش ژنوتیپ Genotype

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

نمایش دودویی :
نمایش دودویی یکی از ساده‌ترین و پر استفاده ترین شیوه‌های نمایش در الگوریتم های ژنتیک است.دراین نوع از نمایش ژنوتیپ شامل رشته ای از بیت‌ها می باشد.برای بعضی از مسائل  زمانی که راه حل شامل متغیرهای تصمیم گیری بولین (yes/no ) می‌باشد نمایش به صورت باینری (دودویی) امری طبیعی است.برای مثال در مسائله کوله پشتی 1/0 (0/1 Knapsack Problem) .اگر n آیتم وجود داشته باشد ، می‌توانیم راه حل را بوسیله یک رشته دودویی از n عنصر نمایش بدهیم ، بطوری که X امین عنصر (x ^th) می‌گوید که آیتم x برداشته شده است (۱) یا خیر (0)

برای مسائل دیگر بویژه مسائلی که با اعداد سر و کار دارند ، می‌توانیم اعداد را به صورت حالت دودویی آن‌ها نشان بدهیم.مشکل با این نوع از رمزگذاری (encoding  ) این است که بیتهای مختلف دارای اهمیت متفاوتی هستند ، بنابراین عملگرهایی مثال جهش (mutation) و متقاطع (crossover ) می‌توانند اثرات ناملطوبی داشته باشند.این مشکل می‌تواند تا حدی با استفاده از Gray Coding حل شود ، بدین صورت تغیر در یک بیت تأثیرات خیلی زیادی در حل مسائله نخواهد داشت.

نمایش مقدار دهی واقعی (Real Valued Representation):
برای مسائلی که می‌خواهیم ژنها را با استفاده از متغیر های متوالی بجای متغیر های گسسته تغریف کنیم ، نمایش مقدار دهی واقعی طبیعی ترین روش است.اگر چه دقت این مقدار دهی واقعی یا نقطه اعشار اعداد یکی از محدودیت‌ها برای کامپیوتر است.در این روش نمایش مقدار هر چیزی مرتبط با مسائله می‌تواند باشد.و هر کروموزم می‌تواند شامل یک مقدار باشد.

نمایش صحیح (Integer Representation)

برای ژنهایی با مقادیر گسسته ، همیشه نمی‌توانیم راه حل را به فضای دودویی yes یا no محدود نماییم.برای مثال اگر با می‌خواهیم چهار مسیر شمال ، جنوب ،شرق و غرب را رمزگذاری کنیم، می‌توانیم آن‌ها را به صورت {۰،۱،۲،۳} رمز گذاری نماییم.در چنین مواردی نمایش صحیحی مورد استفاده است.

نمایش جایگشتی :

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