بخشی از مقاله
طراحی مسیر ربات متحرک
چکیده
این مقاله الگوریتمی جدید برای مسئله برنامه ریزی مسیرکلی به یک هدف ، برای ربات متحرک را با استفاده از الگوریتم ژنتیک ارائه می دهد .الگوریتم ژنتیک برای یافتن مسیر بهینه برای ربات متحرک جهت حرکت در محیط استاتیک که توسط نقشه ای با گره ها و لینک ها بیان شده است ،بکار گرفته شده است.موقعیت هدف و موانع برای یافتن یک مسیر بهینه در محیط دو بعدی داده شده است .هر نقطه اتصال در شبکه ژنی است که با استفاده از کد باینری ارائه شده است.تعداد ژن ها در یک کروموزوم تابعی از تعداد موانع در نقشه (نمودار)می باشد.
بنابراین از یک کروموزوم با طول ثابت استفاده کردیم.مسیر ربات ایجاد شده ، در مفهوم کوتاهترین مسیر ،بهینه است .ربات دارای محل آغاز و محل هدف تحت فرضیه ای است که ربات از هر محل فقط یکبار می گذرد یا اصلا نمی گذرد.نتایج بدست آمده در شبیه سازی ؛قدرت الگوریتم پیشنهادی را تایید می نماید.
مقدمه
مسئله طراحی مسیر ربات متحرک را می توان بصورت ذیل بیان کرد:
داده های مسئله (محل شروع،محل هدف، نقشه اي دو بعدی مسیرهاكه شامل موانع ساكن می باشد).هدف بدست آوردن یک مسير بدون تصادم بین دو نقطه خاص در ایفای معیار بهینه سازی با در نظر گرفتن محدودیت ها (به احتمال زیاد:کوتاهترین مسیر)می باشد. مسئله طراحی مسیر از نظر محاسباتی بسیار پر هزینه است.
با اینکه حجم زیادی از تحقیقات برای حل بیشتر این مسائل انجام شده است،با این وجود،روش های معمول ،غیر قابل انعطاف می باشند.
1.اهداف مختلف بهينه سازي و تغييرات اهداف
2. عدم قطعیت ها در محیط ها
3. محدوديت هاي متفاوت براي منابع محاسباتي
مرور و بازنگری روش های موجود برای حل مسئله طراحی مسیر ،در [1] ارائه شده است . روش هاي زيادي براي ايجاد يك مسير بهينه از قبيل برنامه ريزي ديناميك و روش هاي تبدیل مسافت گزارش شده است .
در روش برنامه ريزي ديناميك اگر نقطه ي شروعSP و نقطه ي هدف GP باشد ، نقطه ي زیر هدف IP است.و روش توليد مسیر ،نحوه تعیین توالی زیر اهداف است که زیر اهداف خود از مجموعه IP (I=1,2,3,…) انتخاب می شوند.ما بايد تمام مسیرهای ممکن را بررسی کرده و مسیر با کمترین مقدار هزینه را به عنوان مسیر بهینه انتخاب نمائیم.توان محاسباتی بسیار فراوانی بویژه در محیط های دارای زیر اهداف فراوان مورد نیاز است . در روش تبدیل مسافت ،کارطراحی مسیر
،محیطی را با شبکه یکنواخت می پوشاند و فواصل را از طریق فضای خالی ،از سلول هدف،منتشر می کند.قسمت پیشین موج مسافت ،حول موانع و در نهایت از طریق تمامی فضاهای آزاد در محیط جریان می یابد.برای هر نقطه شروع در محیط نمایانگر محل اولیه ربات متحرک ،کوتاهترین مسیر به مقصد،از طریق رفتن به قسمت پائین و از طریق شیب دارترین مسیر نزولی رسم شده است.با این وجود به هنگام وجود دو سلول یا بیشتر جهت گزینش با همان حداقل تبدیل فاصله ابهام مسیرهای بهینه وجود دارد. دو روش مذکور ملزم توان محاسباتی بسیار بالا در محیطی است که دارای تعداد زیاد اهداف فرعی (زیر اهداف)و موانع است.
محققان روش های فراوان را برای حل مسائل طراحی مسیر ربات های متحرک با وجود موانع ایستا و متحرک بر مبنای soft computing ،بیان کرده اند. soft
computing متشکل از منطق فازی،شبکه های عصبی و محاسبات تکاملی است (الگوریتم های ژنتیک و تکاملی GA & EA).تاکنون تلاش های زیادی در استفاده از منطق فازی برای طراحی و برنامه ریزی حرکت ربات متحرک وجود داشته است .اخیرا استفاده از محاسبات تکاملی رواج فراوانی پیدا کرده و در واقع روشی است که به منظور بکارگیری در موقعیت هایی که دانش اولیه راجع حل مسئله وجود نداشته و یا اطلاعات محدود می باشد،قابلیت استفاده به گونه ای موثرتر،عمومی تر و راحت تر را داراست.
الگوریتم های ژنتیکی و تکامکلی نیازمند اطلاعات اشتقاقی یا برآوردهای فرمال اولیه از راه حل نیستند و از آنجائیکه طبیعتا تصادفی می باشند دارای قابلیت جستجوی کل فضای جواب با احتمال بیشتر پیدا کردن بهینه عمومی می باشند.
می توان تحقیق قبلی راجع طراحی مسیر را به صورت یکی از دو روش مقابل طبقه بندی کرد: مبتنی بر مدل و مبتنی بر سنسور .
در حالت مبتنی بر مدل ،مدل های منطقی از موانع شناخته شده ،برای تولید تصادم بدون مسیر بکار گرفته می شوند.در حالیکه در روش مبتنی بر سنسور ، کشف و اجتناب از موانع ناشناخته است.در این مقاله الگوریتمی جدید جهت بدست آوردن مسیر بهینه بر مبنای مدل پیشنهاد شده است.
ادامه مطالب مقاله بصورت ذیل مرتب شده اند :
در بخش 2 ،مقدمه ای مختصر راجع الگوریتم ژنتیک ارائه شده است .در بخش 3 ،فرمول سازی مسئله مورد بررسی واقع شده،در بخش 4 الگوریتم پیشنهادی ، معرفی و در بخش 5 نتایج شبیه سازی نشان داده شده است.
1.مسیریابی
مسئله مسیریابی ربات در چند حالت قابل بررسی است :
در یک مفهوم می توان مسیریابی روبات را در قالب تعقیب خط (عموما مسیری از پیش تعیین شده با رنگ متفاوت از زمینه ) معرفی نمود.روبات هایی با این کاربرد تحت عنوان مسیریاب شناخته می شوند . یکی از کاربرد های عمده این ربات ، حمل و نقل وسایل و کالاهای مختلف در کارخانجات ، بیمارستان ها ، فروشگاه ها ، کتابخانه ها و ... میباشد .
ربات تعقیب خط تا حدی قادر به انجام وظیفه کتاب داری کتابخانه ها می باشد . به این صورت که بعد از دادن کد کتاب ، ربات با دنبال کردن مسیری که کد آن را تعیین میکند ، به محلی که کتاب در آن قرار گرفته می رود و کتاب را برداشته و به نزد ما می آورد .مثال دیگر این نوع ربات در بیمارستان های پیشرفته است ، کف بیمارستان های پیشرفته خط کشی هایی به رنگ های مختلف به منظور هدایت ربات های مسیریاب به محل های مختلف وجود دارد . (مثلا رنگ قرمز به اتاق جراحی یا آبی به اتاق زایمان.) بیمارانی که توانایی حرکت کردن و جا به جا شدن را ندارند و باید از ویلچر استفاده کنند ، این ویلچر نقش ربات تعقیب خط را دارد ، و بیمار را از روی مسیر مشخص به محل مطلوب می برد .
با توجه به وجود موانع (استاتیک و دینامیک) در محیط ،مسیریابی روبات در مفهومی کاربردی تر ،پیمودن مسیر مبدا تا مقصد بدون برخورد با موانع می باشد.مسلما با وجود تعداد زیاد موانع ،تعداد مسیرهای قابل عبور روبات بسیار زیاد خواهد بود و یقینا انتخاب کوتاه ترین مسیر توسط روبات برای حرکت از مبدا به مقصد ،دارای ارزش اجرایی بالایی خواهد بود.در این مقاله چنین مسئله ای مورد بررسی واقع شده است.نقاط مبدا و مقصد و نیز محل موانع به عنوان ورودی داده شده است ،نیز می دانیم موانع ایستا می باشند (در حالت وجود موانع پویا در عین نزدیکی بیشتر به شرایط واقعی ،روش های مورد استفاده بسیار
پیچیده خواهند بود)و مسئله در حالت دو بعدی بررسی می شود (روبات بر روی صفحه حرکت می نماید). برای این منظور الگوریتم های مسیریابی با هدف انتخاب کوتاهترین مسیر قابل استفاده می باشند ،الگوریتم هایی که به منظور مسیریابی در شبکه ها قابلیت استفاده دارند.با این وجود در این بررسی از الگوریتم ژنتیک استفاده شده است . همچنین الگوریتم های ژنتیک و نیز دیگر روش های مشابه به منظور بهینه سازی مصرف انرژی روبات ،مسیر تغییر زاویه ازوی روبات ،زمان حرکت روبات و... قابل استفاده می باشند .
2.الگوریتم ژنتیک
GA در سال 1975 توسط Holland بر پایه تقلیدی از تکامل طبیعی یک جمعیت پایه ریزی شد به نحوی که کروموزوم ها به منظور خلق نسل جدید اجازه تولید مجدد داشته و جهت بقاء در نسل آینده به رقابت می پردازند.با گذشت زمان ،بر روی نسل ها ، fitness بهبود می یابد و در نهایت بهترین راه حل قابل حصول است .اولین جمعیت p(0) به طور تصادفی با 0و1 کد می شود در هر نسل ،t، مناسبترین عناصر برای حضور در mating pool انتخاب می شوند و با سه عملگر پایه ای ژنتیک ؛ تولید مثل،ادغام و جهش ؛ جهت تولید نسل جدید تکامل می یابند .بر پایه بقاء بهترین هامی توان نتیجه گرفت کروموزوم های بدست آمده با استفاده از روشی منتخب بهترین کروموزوم ها قابل حصول می باشند.
از جمله مزایای GA که این روش را جهت بکارگیری آن در مورد انتخاب متغیر مناسب می نماید می توان به توانایی پیدا کردن بهینه عمومی با سرعت بالا،امکان جستجو موازی چند نقطه و نیز فرار از بهینه های محلی اشاره نمود.
Procedure
GA
Begin
t=0
initialize p(t)
evaluate p(t)
while not satisfy stopping rule do
begin
t=t+1
select p(t) from p(t-1)
alter(t)
evaluate p(t)
end
end
چنانچه بیان شد عموما تکامل از یک نسل به نسل بعد ،شامل سه مرحله است :ارزیابی تناسب،گزینش و بازآفرینی.
ابتدا ،جمعیت کنونی با استفاده از تابع تکامل تناسب ارزیابی شده و سپس بر اساس مناسب بودنشان طبقه بندی می شوند و در واقع نسل جدید با هدف بهبود و ارتقاء تناسب بوجود می آید.
روش بکار بردن عملگرهای ،تولیدمثل؛جهش و ادغام توسط الگوریتم ژنتیک به شکل زیر است :
در آغاز ، باز آفرینی منتخب ،بر روی جمعیت کنونی بنحو
ی بکار گرفته می شود که رشته ،تعدادی کپی ،بر اساس مناسب بودن آنها تهیه می کند.این عمل منجر به تولید جمعیت میانی خواهد شد. سپس دوما ،الگوریتم ژنتیک والدین را از جمعیت کنونی با احتمال بیشتر در انتخاب کروموزوم های بهتر گزینش می نماید.این عمل همراه با کمیت تناسب و دسته بندی کروموزوم خواهد بود و نهایتا (سوما)،این الگوریتم فرزندان (رشته های جدید)را از والدین منتخب با استفاده از اپراتورهای ادغام یا جهش بازآفرینی می
نماید.اساسا ادغام،شامل تبادل تصادفی بیت هابین دو رشته جمعیت میانی می باشد.در نهایت عملگر جهش ،به طور تصادفی تعدادی از بیت های بین رشته های جدید را تعویض می نماید.این الگوریتم زمانی پایان می یابد که راه حل قابل قبول پیدا شودویا معیار همگرایی ایفا شود و یا وقتی که به تعداد محدود و از پیش تعیین شده تکرار دست یابیم.مشخصه های اصلی الگوریتم های ژنتیک این است که آنها می توانند فضای جستجو را به طور برابر جستجو کنند و نیازی به بهینه سازی تابع برای تمایز گذاشتن یا هرگونه ویژگی یکنواخت ندارند.دقت راه حل اکتسابی به تعداد کد مورد استفاده برای کدگذاری متغیر خاص(طول کروموزوم)بستگی دارد.
3.فرمول سازی مسئله
مسئله به صورت زیر بیان شده است :ربات متحرک در مسیری بسته حرکت می نماید.این ناحیه به صورت نموداری دو بعدی توصیف می شود.چنین نموداری شامل تعداد محدودی موانع ایستا و یک سری نقاط به منظور جلوگیری از برخورد رباتها به موانع است.هدف،طراحی مسیر بهینه بدون هیچ گونه تصادم بین نقطه شروع و نقطه هدف می باشد.به این معنا که باید معیار هدف را با محدودیت عاری از تصادم بهینه سازی کرد .اگر نمودار دو بعدی شامل نقاط اتصال باشد ،فضای کل راه حل های احتمالی ،بسیار بزرگ است .در واقع فضای C هر ربات ، فضای کل پیکربندی های مسیر ربات است .
مسئله طراحی مسیر ، معادل با طراحی حرکت یک نقطه از ربات (نقطه مرجع )در فضای C می باشد.فضای C بدون رخورد ، اشاره به مکان هندسی تمام نقاط فضای C دارد که نمایانگر پیکربندی های عملی و عاری از تصادم است.به این معنا که باید مسیر بهینه عملی و میسر باشد.به طور کل برای پیدا کردن مسیر بهینه بدون تصادم ، سه هدف بهینه سازی متفاوت وجود دارد:
1.به حداقل رساندن مسافت طی شده (کوتاهترین مسیر)
2.حفظ مسیر یکنواخت
3.ایفای ملزومات مشخص (ربات نباید خیلی به موانع نزدیک شود)
شکل 1 موقعیت های مختلف را نشان می دهد
مسیر1.مسیری محتمل در نظر گرفته نمی شود(تصادم مانع)
مسیر2.کوتاهترین مسافت و مسیر محتمل است
مسیر3.میسر بوده و مطمئن تر است (دورترین مسیر از مانع)
مسیر4.میسر است ولی معیار بهینگی را ایفا نمی کند
می توان این اهداف را با عوامل متفاوت،نسبت به اهمیت شان در مسئله بهینه سازی ایستامورد آزمایش قرار داد.در این مقاله بر ارائه کوتاهترین مسیر بدون تصادم،بین نقطه شروع(PS)ونقطه هدف(PG)با استفاده از الگوریتم ژنتیک متمرکز می شویم.
4.الگوریتم طراحی مسیر پیشنهادی
در این بخش ،برای پیدا کردن مسیرهای بهینه برای یک ربات ،جهت حرکت در محیط ایستای بیان شده از طریق یک نمودار با گره ها و لینک ها،الگوریتم ژنتیک بکار رفته است.از موارد کاربرد این مسئله می توان به استفاده از چنین ربات هایی در نمایشگاه ها ،بیمارستان ها ،موزه ها و لابراتوارها برای انتقال مواد اشاره داشت. در الگوریتم پیشنهادی ،هر مسیر از نقطه شروع تا هدف ،جواب است.در آغاز جمعیت های تصادفی از رشته ،تولید شده که نشان دهنده جواب های مجاز (میسر)یا غیر مجاز(غیر میسر)می باشد.جواب های غیر مجاز ، رشته هایی هستند که نمی توانند به هدف برسند.به این معنا که جواب رشته ،ربات را به حرکت در تصادم با موانع ،هدایت می کند.جواب های مجاز ،رشته هایی هستند که می توانند به هدف برسند.برای حرکات ربات متحرک به سمتی که از برخورد با موانع اجتناب نماید باید بهترین رشته ای را بیابیم که هدف را در کوتاهترین مسیر می رساند.
راه حل غیرمجاز دارای کمترین تناسب است (تناسب صفر).نمودار x-y که در مقاله مورد بررسی واقع شده است چنانچه در شکل 2نشان داده شده است ناحیه ای با مساحت 15m¬2 می باشد.
ربات دارای یک نقطه شروع و نقطه هدف روی نمودار ، تحت این فرضیه است که در طراحی مسیر ،ربات از هر نقطه فقط یکبار می گذرد یا اصلا نمی گذرد.هر گره دارای یک عدد در شکل 2 است و گره ها برای رمزگذاری مسیر ،به صورت رشته بیان شده طبق ترتیب اعداد ،بکار می روند.برای مثال0-4-5-10-9-15
یک مسیر با PS=0 و PG=15 می باشد.
با استفاده از الگوریتم ژنتیک، نقاط اتصال ،در آغاز بطور تصادفی انتخاب شده اند،حال آنکه می بایستی اعداد مجاور ، با یک لینک روی نمودار ،بهم متصل باشند.در این زمینه ،اکثر محققان ،رشته مبنی بر ترتیب و دارای طول متغیر (کروموزوم ها)را بکار برده اند.این کروموزوم،از طریق رشته بیت ها ، بازآفرینی شده است (یعنی،نمایش طبیعی و نه دودوئی).بنابراین باید عملگرادغام و جهش خاصی را اتخاذ نمود.هنگام ادغام ،رشته ای که مناسب تشخیص داده شده است ،به طور تصادفی به عنوان یک والد انتخاب می شود.اگر والد دوم شامل عدد مشترکی در رشته اول باشد.یکی از دو رشته ها،بخشی از رشته هایشان را بعد از عدد مشترک مبادله می کنند در غیر اینصورت ،رشته ای دیگر بصورت والدین دوم انتخاب می شود و همین فرآیند دنبال می شود برای مثال با استفاده از نمودار شکل 2 :
والد1:
والد2:
هر والد دارای نقطه مشترک 10 است،بخش زیر خط دار هر رشته مبادله شده و دو مولود بصورت زیر ایجاد می شود
مولود1 : 0-1-5-10-9-15
مولود2 : 0-3-6-4-510-11-12-15
بعد از ادغام ،برای مشخص کردن تکرار یا عدم تکرار عدد در هر رشته ،مولود ها(فرزندان) بررسی می شوند.در اینصورت بخشی از رشته بین ارقام تکراری حذف می شود.سپس اصلاحاتی مورد نیاز است زیرا ممکن است حالتی پیش آید که مولود ها راه حل مجاز نیستند.این روش ،الگوریتم را پیچیده تر می سازد.مسئله مهم،نحوه تولید کدهای دودوئی به گونه ای که استفاده از کروموزوم هایی با طول ثابت عملی و آسان است .یکی از چالش آورترین جنبه های روش پیشنهادی ،کد گذاری هر رشته در کد دودوئی با طول ثابت است .مسیر ربات متحرک با استفاده از اعداد دودوئی کدگذاری شده که در آن هر ژن در یک کروموزوم ،از طریق 4 بیت باینری به گونه ای که در جدول 1 نشان داده شده است ،کدگذاری شده است.
A.كروموزوم ها و جمعیت اولیه
يك كروموزوم ،مطابق با راه حل عملی مسئله بهینه سازی است.بنابراین هر کروموزوم نشان دهنده مسیر است که متشکل از قطعات خط راست می باشد ،به صورت توالی گره ها با اولین گره که نشان دهنده نقطه شروع اولین قطعه ،به دنبال گره های یانی بین قطعات و قطعه آخری نشان دهنده نقطه پایانی قطعه آخری،هدف،می باشد.حداکثر طول کروموزوم پیش فرض ،برابر با تعداد نقاط نمودار در طول ژن است. در این حالت ،16 نقطه داری که هر نقطه در 4 بیت دودوئی کدگذاری شده است.به این معناکه طول کروموزوم برابر با 64=4*16 بیت می باشد.این نتیجه ساده است زیرا می توانیم طول موثر کروموزوم را برای کاستن توان محاسباتی لازم،کاهش دهیم.از توپولوژی نمودار مشاهده کردیم که مسیر بهینه برای رسیدن به نقطه هدف مرتبط با تعداد موانع است .
اگر تعداد موانع ایستا برابر با m باشد،کوتاهترین مسیر متشکل از حداکثر نقاط (m+2)یا تعداد(m+1)تکه خط است.این رابطه می پذیرد که شکل مانع پیچیده نیست و می تواند به صورت نقطه حجم در نظر گرفته شود.
برای مثال اگر هیچگونه مانعی وجود نداشته باشد(m=0)کوتاهترین مسیر متشکل از یک قطعه خطی از نقطه شروع تا هدف است (تعداد نقاط 2)در شکل1،تعداد موانع استا m=3 ؛کوتاهترین مسیر تشکل از 3 نقطه ؛کمتر از 5 (m+2)می باشد.در شکل 2 ،m=7،کوتاهترین مسیر از نقاط 0 تا نقطه 15 {0-4-6-7-9-15} (6 نقطه)می باشد که کمتر از 9 است(m+2).بنابراین معادله زیر برای تعریف طول کروموزوم بکار خواهد رفت. Cn=m+2 که m تعداد موانع ایستا و cn تعداد ژن ها در کروموزوم است.برای نمودار داده شده در شکل2،طول کروموزوم =4*(2+7)بیت دودوئی،می توان جمعیت اولیه کرووزوم ها را به طور تصادفی چنان تولید کرد کههر کروموزوم دارای m ژن تصادفی باشد حال آنکه نقاط آغازین و هدف در جمعیت ثابت شده اند.
.ارزیابیB
معمولا انتخاب تابع ارزیاب بر مسئله تحت شرایط بسیار خاص است.تابع ارزیاب یک کروموزوم،برای محاسبه تعیین مناسب بودن آن بکار می رود .زیرا تناسب باید به صورت کاهش فاصله ،افزایش یابد.بنابراین تابع تناسب F از یک مسیر محتمل بصورت زیرارزیابی شده است.
که در آن d(pi,pi+1) طول قطعه بین دو نقطه pi,pi+1 در کروموزوم با تعداد نقاط m+2 است.
می توان طول قطعه را با استفاده از مقادیر مختصات x-y در جدول 1 به صورت زیر محاسبه نمود
اگر مسیر محتمل نباشد ،مقدار تناسب آن صفر می باشد.الگوریتم پیشنهادی قادر است نقاط مسیر را برای آشکار سازی عملی بودن آن یا عدم عملی بودنش در جدول 2 ,ترسیم نماید.نقاط اتصالی, نقاط مجاز مجاوربه نقاط کنونی در راه حل برای اجتناب از موانع اند.
C.عملگرها
در الگوریتم ,ازدو عملگر ژنتیکی رایج استفاده شده است.ادغام وجهش.ادغام ,دو مسیر "والد" را برای تولید دومسیر جدید "مولود"در نسل بعدی دوباره ترکیب می کند.از ادغام دو نقطه ای استفاده شده است. هردومسیر والد به طور تصادفی به سه بخش تقسیم شده و دوباره ترکیب شده اند.بخش وسطی اولین مسیر بین موقعیت های بیت هی ادغام و بخش میانی دومین مسیر(والد دوم) برای ایجادفرزندان جدید تبادل می شوند,موقعیت های بیت ادغام به طور تصادفی در طول کوروموزوم بین موقعیت های 5.32 انتخاب شده اند.این محدودیت ها,برای عدم اعمال تغییر نقاط اولی و هدف,طی فرآیند ادغام ,انتخاب شده اند.برای مثال ,با مشخص ودن والدین (36 بیت) به صورت زیر ,باید به طور تصادفی در موقعیتهای 15و23 ادغام داده شوند.همچین فرآیند جهش ,برای تغییر تصادفی موقعیت یک بیت در کروموزوم کار برده شده است(بین موقعیت 5و32).شبه کد الگوریتم پیشنهادی بصورت ذیل داده شده است:
5.نتايج شبيه سازي
الگوريتم بالا به منظور شبیه سازی با استفاده از Matlabآزمايش شده است.محیط شبيه سازي دارای دستورات دستکاری رشته ای بسیار موثر است که تبدیل متغیرهای عدی به رشته ای و عکس این حالت را به گونه ای موثر میسر می سازد.در نتیجه عملگرهای ادغام و جهش به راحتی قابل پیاده سازی می باشند.
مثال شبيه سازي شده :
نقطه ي شروع 0 و نقطه ي پايان 15 است شكل 2 به صورت تولید کننده مسیر شبيه سازي شده است .بیت آغازین متشکل از 6 کروموزوم 63 بیتی است.احتمال ادغام 100 درصد در نظر گرفته شده و احتمال جهش 0.005 درصد می باشد.بهترین نتایج با استفاده از دو نقطه ادغام بدست امده است.نتایج شبیه سازی بعد از 50 نسل بصورت زیر داده شده است :
نتيجه ي بالا باينري معادل با جمعيت مسیرها به صورت زیر می باشد.
کروموزوم دومی به علت فرآیند جهش ،تاحدودی متفاوت است.بخشی از اعداد تکراری ،جداشده و نتیجه نهایی کوتاهترین مسیر منفرد{0-4-6-7-9-15}یا مسیر بهینه منفرد با طول 17.975 همگرا شده است.
این مسئله ،با سایر نقاط آغازین تست شده و نقاط نهایی و همگرایی آن،برای بدست آوردن مسیر بهینه در هر مورد ضمانت شده است.
الگوريتم ژنتیک ساده با طول ثابت کروموزوم،برای یک ربات متحرک به منظور دریافت کوتاهترین مسیر در محیط ایستای دو بعدی با M مانع ،شکل گرفته است.الگوریتم توسعه یافته از طرح کدگذاری موثر با رشته دودوئی دارای طول ثابت استفاده می نماید.طول کروموزوم بستگي به تعداد موانع ساكن دارد.هر کروموزوم دارای طول ثابت (m+2)ژن است.این الگووریتم نیازمند توان محاسباتی کمتر از سایر الگوریتمهای اخیرا توسعه یافته است.در محیط های دینامیک لازم است طول کروموزوم متغیر در نظر گرفته شود.
