پیاده سازی الگوریتم بهینه سازی کلونی مورچه در مکانیابی پناهگاه­ های اسکان موقت بعد از زلزله

قسمتی از متن پایان نامه :

1-1-1-  حل مسئله TSP با بهره گیری از الگوریتمACO

الگوریتم مورچه­ها اولین بار برای حل مسئله TSP پسشنهاد شده می باشد. مسئله­ی فروشنده دوره­گرد نمونه­ای رایج از مسائل NP-Complete و یکی از مشهورترین مسائل بهینه سازی ترکیبی می­باشد (Gutin, et al., 2002). فروشنده دوره­گرد می خواهد مشتریان خود را در شهرهای مختلف ملاقات کند و به شهر خود بازگردد. او می­خواهد کوتاهترین مسیر ممکن را برای این کار انتخاب کرده و از هر شهر فقط یکبار دیدن کند. به راحتی می­توان دید که مسئله فروشنده دوره­گرد را می توان به صورت یک گراف کامل وزن­دار G = (C,L) در نظر گرفت که مجموعه C (رئوس گراف) شامل شهرها و مجموعه L(یالهای گراف) شامل جاده­های ارتباطی بین شهر­ها می­باشد. همچنین به هر یال L (i,j)   یک مقدار dij که نشان دهنده فاصله بین شهر i و j می باشد. این مقادیر گراف G را وزن­دار می کنند.

در مسئله فروشنده دوره­گرد اگر برای هر دو راس i و j داشته باشیم dij = dji آنگاه مسئله از نوع متقارن و اگر برای یک یال با هم برابر نباشند مسئله نامتقارن نامیده می گردد. هدف در این مسئله یافتن یک دور همیلتونی با کمترین وزن در گراف متناظر مسئله می باشد( Dorigo, et al., 2002). از آنجایی که TSP یک مسئله بهینه­سازی ترکیبی می­باشد، می توان سه تایی (s,f,Q)  را به صورت زیر در نظر گرفت:

پارامتر f تابعی می باشد که بایستی کمینه گردد و برابر مجموع کل فواصل طی شده در هر دور می باشد، یعنی اگر S  s  یک دور همیلتونی باشد f(s) طول مسافت طی شده تحت این دور می باشد و  Q  نیز مجموعه محدودیت­ها می باشد. در اینجا دور همیلتونی بودن قید مسئله می باشد. الگوریتم مورچه ها مسئله را بصورت مرحله به مرحله و تکراری حل می کند. در هر تکرار، مورچه ها از هر شهر به شهر­های ملاقات نشده حرکت میکنند تا آنکه همه شهرها را پشت سر بگذارند. به محض ورود عامل به یک شهر، اسم آن شهر وارد فهرستی به اسم لیست ممنوعه[1] می گردد و در آن ذخیره میگردد. و به این ترتیب به عامل اجازه داده نمی گردد تا پایان گام t-ام آن شهر را دوباره ملاقات کند. بعد از پایان هر گام این لیست خالی شده و به عامل اجازه داده می گردد در گام­های بعدی این لیست را پر نماید.  مورچه­ها با در نظر داشتن یک قانون احتمالاتی معین، مقصد بعدی­شان را برای حرکت انتخاب می کنند. برای این کار از اطلاعات فرومونی ijτ وȠij بخش ابتکاری الگوریتم بهره می گیرند. هر چه این مقادیر در یک یال بیشتر باشند، یال متناظر با آن بیشتر مورد توجه مورچه ها قرار می گیرد.

[1] Taboo list

سوالات یا اهداف این پایان نامه :

شما می توانید مطالب مشابه این مطلب را با جستجو در همین سایت بخوانید

  • چگونه می توان الگوریتم ACO را در مکانیابی پناهگاه های اسکان موقت پیاده سازی نمود؟
  • آیا امکان تلفیق الگوریتم ACO با روشهای ارزیابی چند معیاره هست؟
  • چگونه می توان تخصیص جمعیت را همزمان با مکانیابی اماکن اسکان موقت در نظر داشت؟

 دانلود متن کامل پایان نامه جغرافیا در لینک پایین صفحه