الگوریتم ژنتیک­جایگشتی
جایگشت، در قلمرو ترکیباتیِ آن، به معنی مرتب‌سازی یا تغییر ترتیب اعضای یک مجموعه می‌باشد. ممکن است این چیدمان خطی و یا غیرخطی (مثلا دور یک دایره که در این حالت «جایگشت دوری»^[۱۳۸] نامیده می‌شود) صورت گیرد. اعضای مجموعه نیز می‌توانند هر چیزی باشند مثلا شی یا عدد یا حرف و هم­چنین می‌توانند تکراری باشند یا متمایز. در هر مورد، مهم، تعداد طرق چیدن این اعضا است (Wikipedia, 2013).

مسائل جایگشت
گاهی اوقات بهینه­سازی شامل مسائلی همچون مرتب کردن یک فهرست یا قرار دادن چیزهایی در جای مناسب می­باشد. در این­جا می­خواهیم با شرح مسأله فروشنده دوره­گرد (TSP) شروع کنیم.
معروف­ترین مسأله ، فروشنده دوره­گردی است کـه می­خواهد به N شهر سفر کند به­ طوری که کم­ترین مسافت ممکن را بپیماید. به هر شهر فقط یک بار سفر می­ کند؛ بنابراین، جواب شامل فهرستی از ترتیب سفر به شهرهاست. هدف یافتن کوتاه ترین مسیری است که برای عبور از N شهر توسط یک فروشنده طی می­ شود. همان­طور که در شکل (۲-۱۱) نشان داده شده است باید به این جواب برسیم که اگر فروشنده دوره‌گرد از نقطه A شروع کند و فواصل بین نقاط مشخص باشد، کوتاه‌ترین مسیر که از تمام نقاط یکبار بازدید می‌کند و به A بازمی‌گردد کدام است؟

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

مسأله TSP به شکل­های گوناگون در علوم مهندسی کاربرد دارد مانند آرایش بهینه خطوط گاز، سامانه تغذیه کننده آنتن، پیکربندی ترانزیستورها بر روی یک مدار مجتمع با مقیاس بزرگ (VLSI)^[139] یا مرتب­سازی اشیاء به منظور مطابقت با یک پیکربندی خاص (شاه­حسینی، موسوی و ملاجعفری، ۱۳۹۱).
شکل(۲-۱۱): مسأله فروشنده دوره­گرد (Wikipedia, 2013)
عملگرهای ادغام و جهشِ استاندارد الگوریتم ژنتیک، برای الگوریتم ژنتیک جایگشتی مناسب نیستند زیرا مثلا در فروشنده دوره­گرد باید اطمینان حاصل کنیم که از هر شهر یک و فقط یکبـار عبور خواهیم کرد. به­همین دلیل روش­های متعددی برای اصلاح عملگرهای ادغام و جهش به منظور مواجهه با مسائل جایگشتی و «مسائل مرتب­سازی مجدد»^[۱۴۰]، ارائه می­گردد (شاه­حسینی، موسوی و ملاجعفری، ۱۳۹۱).
بیایید با مثالی ساده از شش عدد که باید مجددا مرتب شوند، آغاز کنیم. ما در این­جا از اعداد صحیح استفاده می­کنیم، گرچه هرگونه کدگذاری منطقی و متعارفی می ­تواند برای این­منظور بکار رود.
دو کروموزوم والد به طول ۶ را در نظر بگیرید:

یک ادغام ساده بین دومین و سومین عنصر آرایه­های کروموزوم والدین، فرزندان را تولید خواهد کرد.

بدیهی است این روش عملی نیست زیرا فرزند ۱ شامل دو عدد ۳ و فاقد ۱ است در حالی که فرزند ۲ فاقد ۳ و دارای دو عدد ۱ است. گلدبرگ^[۱۴۱] (۱۹۸۹) راه­ حل­های عملیِ متعددی را مورد بررسی قرار داده است که به­ صورت مختصر در این­جا آورده شده ­اند. اولینِ آن­ها «ادغام تطبیق یافته جزئی (PMX)»^[۱۴۲] نام دارد (Goldberg & Lingle, 1985). در این روش، دو نقطه­ی ادغام را انتخاب کرده و کار را با تعویض مقادیر والدین در بین این دو نقطه آغاز می­کنیم. اگر نقاط ادغام بین دو عنصر «۱,۲» و «۳,۴» باشند؛ آن­گاه رشته «a» از والد ۲ با رشته «b» از والد ۱ جابجا می­ شود(شاه­حسینی، موسوی و ملاجعفری، ۱۳۹۱).