کدینگ درختی
کدینگ درختی در برنامه های تکاملی به منظور برنامه ریزی تکاملی بکار می رود. در کدینگ درختی هرکروموزوم یک درخت از اشیائی نظیر توابع یا دستورها در زبان برنامه نویسی می باشد. شکل زیر دو نمونه از این کروموزوم ها را نشان می دهد. این نوع کدینگ برای برنامه های تکاملی بسیار عالی است. اغلب از این نوع کدینگ استفاده می شود و این بدین علت است که برنامه LISP زبان برنامه نویسی های آن به این فرم نمایش داده می شوند و می توانند براحتی مورد تجزیه قرار بگیرند. بنابراین عمل تقاطع و جهش نیز به همان نسبت راحت انجام می شوند.

شکل ۳- ۴: کدینگ درختی

مسائل مربوط به کدینگ
نکته ای که در انتهای این قسمت باید به آن توجه کرد این است که در الگوریتم های ژنتیکی کدینگ یک رابطه بین فضای کدینگ و فضای جواب ها می باشد بطوریکه الگوریتم ژنتیک عملیات تکاملی را بطور متناوب در این دو فضا انجام می دهد(شکل۳-۵). انتخاب طبیعی نیز به عنوان یک رابطه بین کروموزوم ها و عملکرد جواب های کد شده آن ها می باشد.
شکل ۳- ۵: فضای کدینگ و فضای جواب
همانطور که ذکر شد، نحوه کدینگ یک جواب به صورت یک کروموزوم یک موضوع کلیدی در الگوریتم ژنتیک می باشد. در کدینگ های غیر رشته ای سه موضوع بسیار مهم مطرح است که عبارتند از:
قابل قبول بودن کروموزوم
قانونی بودن کروموزوم
رابطه یگانگی
قابل قبول بودن یک کروموزوم به این مفهوم است که آیا دیکدینگ این کروموزوم در ناحیه قابل قبول که جزئی از فضای جواب مساله است قرار دارد یا خیر؟
غیرقابل قبول بودن یک کروموزوم ناشی از طبیعت مسائل بهینه سازی با محدودیت می باشد. معمولاً در مسائل بهینه سازی فضای قابل قبول بوسیله یک سیستم معادلات یا نامعادلات تشکیل می شود. درمتعددی به منظور جلوگیری از ایجاد چنین مواردی روش های جریمه ای کروموزوم های غیرقابل قبول پیشنهاد شده است. در مسائل بهینه سازی با محدودیت عموماً جواب در فضای جواب در مرز بین فضای قابل قبول و فضای غیرقابل قبول قرار دارد. در نتیجه روش های جریمه ای الگوریتم ژنتیک را مجبور می کنند که از هر دو طرف به سمت جواب حرکت کند.
مرز بین فضای قابل قبول و فضای غیرقابل قبول قرار دارد. در نتیجه روش های جریمه ای الگوریتم ژنتیک را مجبور می کنند که از هر دو طرف به سمت جواب حرکت کند. قانونی بودن یک کروموزوم به این مفهوم است که آیا این کروموزوم دراثر دیکدینگ به یک جواب منجرخواهد شد یا خیر ؟ یعنی در فضای جواب قرار خواهد گرفت یا خیر؟غیر قانونی بودن یک کروموزوم ناشی از طبیعت روش های کدینگ می باشد. چون یک کروموزوم غیرقانونی قادر نیست به یک جواب تبدیل شود، در نتیجه ارزیابی چنین کروموزومی غیر ممکن است و بنابراین روش های جریمه ای در اینجا عملی نیستند. در چنین مواردی معمولاً از روش های تعمیری به منظور تبدیل کروموزم های غیر قانونی به کرومزوم های قانونی استفاده می کنند.
شکل ۳- ۶: رابطه بین کروموزوم ها و جواب ها
مساله سوم، بحث یکسانی رابطه است. روابط بین کروموزوم ها و جواب ها معمولاً به یکی از سه صورت زیر است:
رابطه یک به یک
رابطه یک به n
رابطه n به یک
شکل ۳-۷ این سه نوع رابطه را نشان می دهد. از این سه نوع رابطه، رابطه یک به یک بهترین نوع رابطه و رابطه n به یک بدترین نوع آن است.
شکل ۳- ۷: انواع روابط بین کروموزوم ها و جواب ها

کروموزوم
رشته یا دنباله ای از بیت ها که به عنوان شکل کد شده یک جواب ممکن(مناسب یا نامناسب) از مساله مورد نظر می باشد، را کروموزوم می گویند. در حقیقت بیت های یک کروموزوم، نقش ژن ها رادر طبیعت عضوی انتخاب می شود. هر بیت، متغیری گسسته است که از یک مجموعه Q عضوی انتخاب می شود چنانچه از کدگذاری باینری استفاده شود، هر بیت یکی از دو مقدار ٠ یا ١ را می پذیرد.
شکل ۳- ۸: نمایش یک کروموزوم n بیتی

جمعیت
مجموعه ای از کروموزوم ها را جمعیت گویند. یکی از ویژگی های ژنتیک این است که به جای تمرکز برروی یک نقطه از فضای جستجو یا یک کروموزوم، بر روی جمعیتی از کروموزوم ها کار می کند. بدین ترتیب در هر مرحله، الگوریتم دارای جمعیتی از کروموزوم ها بوده که خواص مورد نظر را بیشتر از جمعیت مرحله قبل دارا می باشد. هر جمعیت یا یک نسل از کروموزوم ها، دارای یک اندازه می باشد که به اندازه جمعیت معروف است. اندازه جمعیت معرف تعداد کروموزوم های موجود درجمعیت یا یک نسل است. اگر تعداد کروموزوم ها خیلی کم باشد، امکان شکل گیری عملیات جابجایی توسط الگوریتم ژنتیک بسیار کم خواهد بود و تنها قسمت کمی از فضای جستجو مورد کاوش قرار خواهد گرفت. از طرف دیگر، اگر تعداد کروموزوم ها خیلی زیاد باشد، الگوریتم بسیار کند خواهد شد. بر اساس تحقیقات، جمعیت های با اندازه مناسب حدود ٢٠ تا ٣٠ کروموزوم دارند. البته گاهی اوقات جمعیت با اندازه ۵٠ تا ١٠٠ بهترین جواب ها را داده اند. بعضی تحقیقات نیز نشان می دهد که اندازه جمعیت باید بر اساس نوع مساله و کدینگ آن تعریف شود و افزایش بیشتر آن بی فایده خواهد بود و هرگز به حل سریعتر مساله کمک نمی کند.

مقدار برازندگی
مناسب بودن یا نبودن جواب، با معیاری که از تابع هدف بدست می آید، سنجیده می شود. هر چه که یک جواب مناسب تر باشد، مقدار برازندگی بزرگتری دارد. برای آنکه شانس بقای چنین جوابی بیشتر شود، احتمال بقای آن، متناسب با مقدار برازندگی آن در نظر گرفته می شود. بنابراین کروموزمی که برازنده ترین است با احتمال بیشتری در تولید فرزندان شرکت می کند و دنباله های بیشتری از آن به وجود می آید. به عنوان مثال چنانچه هدف بیشینه کردن یک تابع باشد، مقدار برازندگی، یک تابع صعودی از تابع هدف در نظر گرفته می شود و اگر هدف یافتن مقدار کمینه یک تابع باشد، عدد برازندگی، یک تابع نزولی از آن قرار داده می شود. معمولاً در مواردی که امکان دارد، تابع برازندگی را در فاصله [١ و ۰] نرمالیزه می کنند.

عملگر تقاطعی
این عملگر بر روی یک جفت از کروموزوم ها عمل می کند و می تواند به صورت تک نقطه ای، چند نقطه ای و یکنواخت باشد . عملگر تقاطعی تک نقطه ای، دو کروموزوم را به طور تصادفی از یک نقطه شکسته و بخش های شکسته دو کروموزوم را جابجا می کند. بدین ترتیب دو کروموزوم جدید بدست می آید. به کروموزوم های اولیه، کروموزوم های”والد“ و به کروموزوم های حاصل شده از عمل جابجایی وعمل جهش، کروموزوم”فرزند“می گویند.
عملگر تقاطعی با احتمال P_C بر روی کروموزوم های والد عمل می کند. بدین معنی که با احتمال P_C عمل تقاطع انجام می گیرد. اگر هیچ تقاطعی صورت نگیرد، فرزندان دقیقًا مشابه والدین خواهند بود(البته این مطلب بدین معنی نیست که نسل جدید همان نسل قبلی است). در صورتی که عمل تقاطع صورت بگیرد، فرزندان از قسمت های مختلف کروموزوم های والد ساخته می شوند. اگر احتمال تقاطع ١ باشد، تمامی فرزندان از طریق عمل تقاطعی ایجاد می شوند. عملیات تقاطع با این هدف انجام می شود که کروموزوم های جدید در بردارنده قسمت های مناسب و خوب کروموزوم های قبلی خواهند بود و شاید این کروموزوم های جدید عملکرد بهتری داشته باشند اما بهتر است همیشه بهترین کروموزوم های نسل قبلی بدون هیچ تغییری به نسل جدید منتقل شوند.
معمولاً اگر کروموزوم از کدگذاری چند متغیر به وجود آمده باشد، بهتر است که نقطه جابجایی، محل اتصال متغیرها انتخاب شود. در شکل ۳-۹ کروموزوم ها از شکل کد شده متغیرهای x و y و z وw ساخته شده اند. محل اتصال متغیرها می تواند به عنوان نقطه تقاطع استفاده شود. به طور مثال در شکل ۳-۹ ، محل اتصال متغیرهای x و y به عنوان نقطه تقاطع انتخاب شده است.
شکل ۳- ۹: تقاطع در کرموزوم هایی که از شکل کد شده چهار متغیر به وجود آمده اند.
تفاوت عملگر چندنقطه ای در مقایسه با عملگر تقاطعی تک نقطه ای در این است که نقطه شکست دو کروموزوم، بیش از یکی است و تقاطع در بخش های شکسته شده دو کروموزوم به صورت یک در میان انجام می گیرد. معادله ی زیر مثالی از عمل تقاطع دو نقطه ای را نشان می دهند.
١١٠٠١٠١١ + ١١٠١١١۰١ = ١١٠١١١١١
در عمل تقاطعی یکنواخت، بیت ها به صورت تصادفی از والد ١ یا والد ٢ کپی می شوند.
١١٠٠١٠١١ + ١١٠١١١٠١ = ١١٠١١١١١
باید خاطر نشان ساخت که اثر استفاده از هر کدام از انواع عملگرهای تقاطعی در سرعت همگرایی الگوریتم، دقیقاً مشخص نمی باشد و به مساله مورد نظر بستگی دارد.

عملگر جهشی
این عملگر روی هر یک از کروموزوم های حاصل از عملگر تقاطعی عمل می کند. بدین ترتیب که به ازای هر بیت از کروموزوم، یک عدد تصادفی تولید می گردد. اگر مقدار این عدد تصادفی از مقدار P_m (احتمال انجام جهش) کمتر باشد، در آن بیت عمل جهش انجام می شود و در غیر اینصورت، در آن بیت عمل جهش انجام نمی گیرد. عمل جهش در هر بیت با تولید تصادفی عدد ٠ یا ١ و جایگزینی آن بجای بیت مورد جهش انجام می گیرد.