No category

منابع و ماخذ تحقیق مدل پیشنهادی، الگوریتم ژنتیک، وسیله نقلیه

(3-1)
∑_(m=1)^R▒∑_(i=1)^n▒〖X_i0^mk=1〗 ∀ k (3-2)
∑_(m=1)^R▒∑_(j=1)^n▒〖X_0j^mk=1〗 ∀ k (3-3)
∑_(k=1)^V▒∑_(m=1)^R▒∑_(j=0,≠i)^n▒〖X_ij^mk +∑_(k=1)^V▒∑_(m=1)^R▒∑_(m^’=1,≠m)^R▒∑_(j=1,≠i)^n▒Y_ij^mm’k 〗=1 ∀ i≠0 (3-4)
∑_(k=1)^V▒∑_(m=1)^R▒∑_(i=1,≠j)^n▒〖X_ij^mk +∑_(k=1)^V▒∑_(m=1)^R▒∑_(m^’=1,≠m)^R▒∑_(i=1,≠,j)^n▒Y_ij^mm’k 〗=1 ∀ j≠0 (3-5)
∑_(i=0,≠j)^n▒〖X_ij^mk+∑_(i=1,≠j)^n▒∑_(m^’=1,≠m)^R▒Y_ij^mm’k 〗=∑_(h=0,≠j)^n▒〖X_jh^m’k+∑_(h=1,≠j)^n▒∑_(m”=1,≠m’)^R▒Y_jh^m’m”k 〗 ∀ j≠0,m,k (3-6)
s_j≥s_i+1-M(1-∑_(k=1)^V▒∑_(m=1)^V▒X_ij^mk -∑_(k=1)^R▒∑_(m^’=1)^R▒∑_(m=1)^R▒Y_ij^(mm^’ k) )
∀ i≠0,j≠0,i≠j (3-7)
T_j≥T_i+(d(i,j)/v(k) )+(st(j)/p(mj) )+M(X_ij^mk-1) ∀ i,j≠0,i≠j,m,k (3-8)
T_j≥T_i+((d(i,0)+d(0,j))/v(k) )+(st(j)/p(m^’ j) )+M(Y_ij^mm’k-1)
∀ i,j≠0,i≠j,m,m^’,k (3-9)
X_ij^mk+Y_ij^mm’k≤g(k,j) ∀ i,j,m,m’,k (3-10)
X_ij^mk+Y_ij^m’mk≤M×p(m,j) ∀ i,j,m,m’,k (3-11)
T_i≤l(i)+M×n_i ∀ i≠0 (3-12)
T_i≥l(i)+M×(n_i-1) ∀ i≠0 (3-13)
X_ij^mk, Y_ij^mm’k, n_i ∈{0,1} (3-14)
معادله (3-1) نشان دهنده تابع هدف مدل است که شامل هزینههای خدمتدهی به مشتریان توسط تیمها و هزینههای جابجایی توسط وسایل نقلیه و همینطور هزینههای دیرکرد میباشد. محدودیت (3-2) و (3-3) بیان کننده این هستند که تمام وسایل نقلیه باید از مرکز پخش مسیر خود را شروع کنند و در انتهای مسیرشان به مرکز پخش بازگردنند. محدودیتهای (3-4) و (3-5) نشان میدهند که به هر مشتری تنها یک وسیله و یک تیم وارد و از آن خارج میشوند. محدودیت (3-6) بیان کننده این است که همان وسیله و تیم ورودی به هر مشتری ، باید از آن خارج شوند. محدودیت (3-7) محدودیت مورد نیاز جهت جلوگیری از ایجاد زیرتور است. محدودیتهای (3-8) و (3-9) بیان کننده ارتباط زمان خدمتدهی بین مشتریان متوالی در یک تور میباشد. محدودیتهای (3-10) و (3-11) محدودیتهای شدنی بودن مسأله هستند و به ترتیب مربوط به توانایی وسیله نقلیه و توانایی تیم برای خدمتدهی به یک مشتری هستند. محدودیتهای (3-12) و (3-13) نشان دهنده ارتباط بین زمان اتمام خدمتدهی به هر مشتری نسبت به موعد زمانی تعریف شده برای آن است.
3-3. روش حل مدل پیشنهادی
مدل پیشنهادی به دنبال کمینه کردن هزینههای جابجایی ، خدمتدهی و دیرکرد میباشد. در واقع هدف تعین تورهای وسایل نقلیه و تخصیص تیمها به مشتریان و پس از آن برنامهریزی همزمان مسیرهای وسایل نقلیه و تیمها به گونهایی است که به تمام مشتریان موجود در سیستم خدمتدهی انجام شود و همینطور هزینههای کل حداقل شود. مدل پیشنهادی جهت صحهگذاری و اطمینان توسط برنامه 11 CPLEX حل شده است. اما برای مسائل تولید شده در ابعاد بزرگتر از الگوریتم فرا ابتکاری ژنتیک بهره برده شده است. در ادامه به معرفی این الگوریتم و همینطور نحوه استفاده از آن برای حل مدل پیشنهادی پرداخته شده است.
3-4. الگوریتم ژنتیک 36(GA)
3-4-1. تعریف
از سال 1960 تقليد از پديده‌هاي طبيعي براي استفاده در الگوريتم‌هاي قوي جهت حل مسايل مشکل بهينه‌سازي مورد توجه قرار گرفت که تکنيک‌هاي محاسبه تکاملي37 نام گرفتند. الگوريتم ژنتيک که اولين بار توسط جان هالند [34] در دانشگاه ميشيگان پيشنهاد شد و استراتژي‌ها و برنامه‌ريزي‌هاي تکاملي که توسط رچنبرگ38 و چيفل39 و فوگوگل40 و کوزا41 ايجاد شدند، از جمله روش‌هاي محاسبه تکاملي هستند.
روش‌هاي بهينه‌سازي الهام گرفته از طبيعت با روش‌هاي متعارف بهينه‌سازي تفاوت مهمي دارند. در روش‌هاي متعارف هرجواب کانديداي جديد در صورتي به عنوان جواب جديد انتخاب مي‌شود که مقدار تابع هدف را بهبود بخشد ولي در الگوريتم‌هاي الهام گرفته از طبيعت به تمام جواب‌هاي کانديداي جديد شانس انتخاب داده مي‌شود.
الگوريتم ژنتيک يکي از مهم‌ترين الگوريتم‌هاي ابتکاري مي‌باشد که از آن براي بهينه‌سازي توابع مختلف استفاده مي‌شود. در اين الگوريتم اطلاعات گذشته با توجه به موروثي ‌بودن الگوريتم استخراج شده و در روند جستجو مورد استفاده قرار مي‌گيرد.
ابتدا توسط هالند [34] يک مفهوم اوليه از الگوريتم ژنتيک ارائه شد و سپس گلدبرگ [35] آن را توصيف کرد. الگوريتم‌هاي ژنتيک، تکنيک‌هاي جستجوي تصادفي هستند که بر اساس انتخاب طبيعي و نسل‌شناسي طبيعي کار مي‌کنند.
اين الگوريتم‌ها تفاوت‌هايي اساسي با روش‌هاي جستجو و بهينه‌سازي متداول دارند که گلدبرگ اين تفاوت‌ها را به صورت ذيل خلاصه کرده است [35].
الگوريتم ژنتيک با مجموعه‌اي از جواب‌هاي کدگذاري شده کار مي‌کند نه با خود آنها.
الگوريتم ژنتيک در يک جمعيت از جواب‌ها و با مجموعه‌اي از آنها شروع به جستجو مي‌کند نه با يک جواب.
الگوريتم ژنتيک از اطلاعات تابع برازش استفاده مي‌کند، نه از مشتق‌ها و يا علوم کمکي ديگر.
الگوريتم ژنتيک از قواعد انتقال احتمالي استفاده مي‌کند نه از قواعد قطعي.
3-4-2. گذري بر ژنتيک طبيعي
در طبيعت فرآيند تکامل هنگامي ايجاد مي‌شود که چهار شرط زير برقرار باشد [34] :
يک موجود توانايي تکثير خود را داشته باشد.
يک جمعيت از چنين موجوداتي که قابليت توليد خود را دارند، وجود داشته باشد.
تنوع در بين اين موجودات وجود داشته باشد.
انواع اين موجودات توسط بعضي از قابليتها، در زندگي محيط اطرافشان از هم مجزا شوند.
در طبيعت تنوع موجودات در اختلافي است که در کروموزومهاي آنها وجود دارد و اين تفاوت در ساختار و رفتار افراد يک جمعيت باعث قدرت بقاي متفاوت مي‌شود. چرا که تنوع ساختار و رفتار به نوبه خود بر روي نرخ زاد و ولد اثر مي‌گذارد. موجوداتي که توانايي بيشتري را در انجام فعاليت‌ها در محيط دارند (براي مثال موجودات متکامل)، داراي نرخ زاد و ولد بالاتري هستند و طبعا موجوداتي که برازندگي يا تطابق42 کمتري با محيط دارند، داراي نرخ پايينتري از زاد و ولد هستند. بنابراين با گذشت زمان تعداد نفراتي که رفتار و ساختار مناسب‌تري دارند افزايش مي‌يابد و جمعيت رو به بهبودي و تکامل مي‌رود. بر اساس اين مفهوم از تکثير بقاي طبيعي و تکثير بقاي احسن که به وسيله چارلز داروين (1859)، بيان شده است، بعد از چند دوره زماني و گذشت چند نسل، کل جمعيت تمايل دارد موجوداتي را بيشتر در خود داشته باشد که با تغيير کروموزوم‌هايشان، ساختار و رفتار آنها قادر به انجام بهتر کارها در محيط و توليد مثل بهتر باشد. بنابراين در طي زمان، ساختار افراد جامعه به علت بقاي طبيعي تغيير مي‌کند. هنگامي که اين تفاوتهاي قابل اندازه‌گيري در ساختار افراد که ناشي از تطابق با محيط اطراف است ديده شود مي‌گوييم که جمعيت تکامل يافته است. در اين فرآيند، ساختار توسط تطبيق مشخصات افراد جامعه با محيط ايجاد مي‌شود.
هنگامي که جمعيتي از موجودات داريم، وجود تفاوت‌ها در آنها به طور غيرمستقيم در نرخ تکثير آنها تاثير مي‌گذارد که اين امر غير قابل اجتناب است. بنابراين در عمل، وجود شرط اول از چهار شرط بالا، شرط اساسي براي شروع فرآيند تکامل است.
جان هالند [34]، قالبي کلي براي تمام سيستم‌هاي قابل تطبيق ايجاد کرد و نشان داد چگونه مي‌توان فرآيند تکامل را براي سيستم‌هاي مصنوعي بکار برد. به طور کلي هر مسأله قابل تطبيق مي‌تواند در قالب واژه‌هاي ژنتيک فرمول‌بندي شود. اگر فرمول‌بندي اين گونه مسايل بر اساس واژه‌هاي ژنتيک باشد، مي‌توانيم آنها را بوسيله الگوريتم‌هاي ژنتيک حل کنيم.
الگوريتم ژنتيک، الگوريتمي رياضي است که با استفاده از الگوهاي عملياتي دارويني در مورد تکثير بقاي احسن و بر اساس فرآيند طبيعي ژنتيک، مجموعه‌اي (جمعيتي) از اشيا منفرد رياضي (معمولا رشته‌هاي کارکتري با طول ثابت به عنوان رشته کروموزوم‌ها) با ميزان تطبيق خاصي را به جمعيت جديدي (براي مثال نسل بعد) تبديل مي‌کند.
الگوريتم ژنتيک در واقع تلاشي براي شبيه‌سازي برخي از خصوصيت‌هاي تکامل و تغييرات روي کروموزوم است که همواره در طبيعت صورت مي‌گيرد. به عبارت ديگر اينها الگوريتم‌هاي شديدا موازي هستند که سعي مي‌کنند با وراثت و جهش طي نسل‌هاي متوالي عملکرد مورد نظري را در افراد يک جمعيت ايجاد کنند. اين کار از طريق ايجاد يک جمعيت اوليه و فراهم آوردن شرايط تکامل در نسل‌هاي بعدي صورت مي‌گيرد.
اولين تئوري مربوط به تکامل در يک جمعيت توسط لامارک43 مطرح شد. طبق اين تئوري صفات اکتسابي موجودات زنده به نسل بعد منتقل مي‌شود. بنابراين اگر موجودات بخواهند با طبيعت خود تطبيق پيدا کنند اين کار عملي خواهد بود. با توجه به تئوري داروين که قبلا به آن اشاره شد مي‌توان به نکات زير رسيد [34] :
وراثت: موجود زنده شبيه خود را مي‌سازد و يا توليد مثل مي‌کند. از لحاظ رياضي يعني تجربه‌هاي قبلي حفظ مي‌شوند.
علل تصادف: در اين همانندسازي يکسري تصادف‌ها و خطاهايي رخ مي‌دهد و به لحاظ رياضي اطلاعات به سيستم يا دستگاه تزريق مي‌شود.
اصل انتخاب طبيعي: موجوداتي که شانس تطبيق بيشتري با طبيعت دارند بقاي بهتري دارند، يعني طبيعت شانس نابرابر براي بقا به موجودات مي‌دهد.
با توجه به اين مطالب شکل کلي تئوري داروين را مي‌توان به صورت شکل (3-1) مدل کرد.
به طور خلاصه الگوريتم ژنتيک را مي‌توان به صورت زير از فرآيند تطابق طبيعي استنتاج کرد:
همانطور که خصوصيات ارثي موجودات زنده بوسيله ژن‌ها بر روي کروموزوم‌ها، رمزگذاري شده‌اند هر يک از پاسخهاي ممکن را نيز مي‌توان بوسيله رشته‌هاي عددي در سيستم دودوئي رمزگذاري کرد و جمعيتي از رشته‌هاي عددي فوق را به عنوان نامزدهاي حل مسأله در نظر گرفت.
در سيستم‌هاي طبيعي، عدم قابليت بقا و سازش ژن، سبب تغيير کثرت نسبي ژن‌ها به نفع ديگر ژن‌ها و بالعکس قابليت بقا و سازش ژن مذکور، کثرت نسبي ژن‌ها را به نفع همين ژن تغيير مي‌دهد. از طريق کثرت نسبي ژن‌ها، انتخاب طبيعي سبب تجمع تنوعات مفيد مي‌گردد. مشابه با اين وضعيت، قابليت بقاي هر رشته جمعيت، توسط ميزان انطباق آن رشته با شرايط مسأله سنجيده مي‌شود. در الگوريتم ژنتيک، مسأله و شرايط آن به مثابه محيط در نظريه تکاملي انواع است. اطلاعات و شرايط مسأله در تابعي به نام تابع ارزيابي گنجانيده و با تخصيص هر يک از رشته‌هاي جمعيت به عنوان

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *