دانلود رایگان ترجمه مقاله الگوریتم ژنتیک چند هدفی در برنامه زمان بندی جریان کارگاهی (نشریه الزویر ۱۹۹۶)
این مقاله انگلیسی ISI در نشریه الزویر در ۱۲ صفحه در سال ۱۹۹۶ منتشر شده و ترجمه آن ۱۸ صفحه میباشد. کیفیت ترجمه این مقاله ارزان – نقره ای ⭐️⭐️ بوده و به صورت کامل ترجمه شده است.
دانلود رایگان مقاله انگلیسی + خرید ترجمه فارسی | |
عنوان فارسی مقاله: |
الگوریتم ژنتیک چند هدفی و کاربردهای آن در برنامه زمان بندی جریان کارگاهی |
عنوان انگلیسی مقاله: |
Multi-objective genetic algorithm and its applications to flowshop scheduling |
|
مشخصات مقاله انگلیسی (PDF) | |
سال انتشار | ۱۹۹۶ |
تعداد صفحات مقاله انگلیسی | ۱۲ صفحه با فرمت pdf |
رشته های مرتبط با این مقاله | مهندسی صنایع، مهندسی کامپیوتر |
گرایش های مرتبط با این مقاله | بهینه سازی سیستم ها، برنامه ریزی و تحلیل سیستم ها، مهندسی الگوریتم ها و محاسبات |
چاپ شده در مجله (ژورنال) | مهندسی صنایع و کامپیوتر – Computers & Industrial Engineering |
ارائه شده از دانشگاه | گروه مهندسی صنایع، دانشگاه Osaka Prefecture، ژاپن |
رفرنس | دارد ✓ |
کد محصول | F1547 |
نشریه | الزویر – Elsevier |
مشخصات و وضعیت ترجمه فارسی این مقاله (Word) | |
وضعیت ترجمه | انجام شده و آماده دانلود |
تعداد صفحات ترجمه تایپ شده با فرمت ورد با قابلیت ویرایش | ۱۸ صفحه (۱ صفحه رفرنس انگلیسی) با فونت ۱۴ B Nazanin |
ترجمه عناوین تصاویر و جداول | ترجمه شده است ✓ |
ترجمه متون داخل تصاویر | ترجمه نشده است ☓ |
ترجمه متون داخل جداول | ترجمه نشده است ☓ |
درج تصاویر در فایل ترجمه | درج شده است ✓ |
درج جداول در فایل ترجمه | درج شده است ✓ |
درج فرمولها و محاسبات در فایل ترجمه | به صورت عکس درج شده است ✓ |
منابع داخل متن | درج نشده است ☓ |
کیفیت ترجمه | کیفیت ترجمه این مقاله متوسط میباشد |
فهرست مطالب |
چکیده |
بخشی از ترجمه |
چکیده
در این مقاله الگوریتم ژنتیک چند هدفی ارائه می کنیم و آن را به برنامه زمانبندی flowshop اعمال می کنیم. ویژگی های مشخصه الگوریتم ما رویه انتخاب آن و استراتژی نگهداری نوابغ آن است. رویه انتخاب در الگوریتم ژنتیک چند هدفی ما افراد را برای عملیات متقاطع برگزیده بر مبنای مجموع وزن دهی شده توابع چند هدفی با وزن های مختلف انتخاب می کند. استراتژی حفظ نوابع در الگوریتم ما از راه حل های چندنخبه ای به جای انتخاب یک نخبه منفرد استفاده می کند. یعنی، تعداد مشخصی از افراد از مجموعه آزمایشی از راه حل های بهینه Pareto انتخاب شده اند و در نسل افراد نابغه بعدی جایگزین شده اند. برای نشان دادن اینکه مشی ما می تواند مسائل بهینه سازی چند هدفی را با نماهای Pareto کاو کنترل و اداره نماید، ما الگوریتم ژنتیکی پیشنهادی را به یک مسئله بهینه سازی تابع دو هدفی با نمای Pareto کو اعمال می کنیم. در نهایت، عملکرد الگوریتم ژنتیک چند هدفی ما با اعمال آن به مسئله برنامه زمانبندی Flowshop آزموده شده است: برای به حداقل رساندن زمان اتمام آخرین کار و به حداقل رساندن و به حداقل رساندن تأخیر مجموع. علاوه بر این ما الگوریتم خود را به مسأله برنامه زمانبندی flowshop با سه هدف اعمال می کنیم: به حداقل رساندن زمان اتمام آخرین کار، به حداقل رساندن دیرکرد مجموع، و به حداقل رسان زمان روند (گردش) مجموع.
۱- مقدمه
مسائل برنامه زمانبندی flowshop یکی از معروفترین مشکلات در حوزه برنامه زمانبندی هستند. از کار جانسون به بعد هدف به حداقل رساندن زمان اتمام آخرین کار به عنوان شرایط زمانبندی flowshop بکار رفته است. مشی های اکتشافی مختلف و همچنین تکنیک های بهینه سازی برای به حداقل رساندن زمان اتمام آخرین کار پیشنهاد شده اند. در حالیکه این مطالعات هدف منفردی را بهبود می دهند، مسائل جهان واقعی متعددی شامل چندین هدف می شوند. اخیراً چند محقق مسائل زمانبندی flowshop چند هدفی را حل کرده اند. به عنوان مثال، Ho و Chan روش اکتشافی برای زمانبندی flowshop با دو شرط ارائه کرده اند، Gangadharan و همکارانش زمانبندی اکتشافی سخت شبیه سازی شده را برای زمانبندی flowshop با دو شرط ارائه کرده اند، و Morizawa و همکارانش روش نمونه گیری تصادفی پیچیده ای برای مسائل چند منظوره (هدفی) ارائه کرده اند.
الگوریتم های ژنتیک عمدتاً برای مسائل بهینه سازی تک هدفی به کار رفته اند. وقتی الگوریتم ژنتیک تک هدفی را به مسأله بهینه سازی چند هدفی اعمال می کنیم باید چندین تابع هدف را در یک تابع تناسب عددی تلفیق کنیم. اگر وزن ثابتی به هر یک از چند تابع هدف برای تلفیق آنها اختصاص دهیم، جهت جستجو در الگوریتم ژنتیک در فضای هدف چند بعدی، به گونه ای که در شکل ۱ نشان داده شده است ثابت می ماند. در شکل ۱، f1(0) یک تابع هدف است که باید بیشینه شود و f2(0) در حال بیشینه شدن است. چرخه بسته موجود در شکل ۱ نشان دهنده راه حل نهایی با الگوریتم ژنتیک تک هدفی است. پس از کار Schaffer برخی مطالعات سعی در طراحی الگوریتم های ژنتیک چند منظوره کرده اند. Schaffer الگوریتم ژنتیک ارزیابی شده برداری (VEGA) را برای یافتن راه حل های بهینه Pareto مسائل بهینه سازی چند هدفی پیشنهاد کرده است. در VEGA ی Schaffer گروهی به زیرگروه های مجزا تقسیم شده بود، سپس هر زیر گروه توسط تابع هدف خود اداره و کنترل گشته بود. اگرچه Schaffer نتایج موفقیت آمیزی از کار خود گزارش کرده است، اما به نظر می رسد روش او تنها قادر به یافتن راه حل های فوق العاده در دیدگاه های Pareto می باشد، درست همان طور که در شکل ۲ نشان داده است چون جهات تحقیق او موازی با محورهای فضای هدف هستند. Schaffer دو روش برای بهبود مشی خود در مقاله اش ارائه کرده است. یکی از این روش ها ارائه اولویت انتخاب اکتشافی برای افراد چیره نشده در هر نسل است. دیگری پیوند زدن میان گونه ها با اضافه کردن چند انتخاب جفت است. نکته مسائل بهینه سازی چند هدفی این است که چگونه تمام تبادلات ممکن میان چند تابع هدف را بیابیم که معمولاً با هم تناقض دارند. چون انتخاب راه حل منفردی برای ی مسأله بهینه سازی چند هدفی بدون تعاملات تکراری با ایجاد کننده جهت مشکل است، مشی معمول و کلی نشان دادن مجموعه راه حل های بهینه Pareto برای تصمیم گیرنده است. پس از آن تصمیم گیرنده می تواند هر یک از راه حل های بهینه Pareto را انتخاب کند. برای درک تمام راه حل های بهینه Pareto با الگوریتم های ژنتیک، انواع مختلفی از افراد را باید در هر نسل نگاه داشت. اخیراً Gen و همکارانش الگوریتم ژنتیکی برای حل یک مسأله حمل و نقل دو ظری ارائه داده اند، Tamaki و همکارانش الگوریتم ژنتیکی برای مسائل زمانبندی با چنند شرط پیشنهاد داده اند، و Horn و همکارانش الگوریتم ژنتیک Pareto ی پسرفت را با مشارکت دادن مفهوم تفوقPareto در رویه انتخاب و اعمال فشار عقب نشینی برای پشت سر گذاشتن گروه در بخش های پیشروی Pareto ارائه داده اند. در این مقاله کا الگوریتم ژنتیک چند منظوره را با جهات تحقیق مختلف، به گونه ای که در شکل ۳ نشان داده شده است ارائه می کنیم. دو ویژگی مشخصه در الگوریتم ما وجود دارد. یکی از آنها رویه انتخاب است. در رویه انتخاب، الگوریتم ژنتیک چند منظوره ما از مجموه وزن دهی شده چند تابع هدف برای تلفیق آنها در یک تابع تناسب عددی استفاده می کند. وزن های الصاق شده به چند تابع هدف ثابت نیستند، بلکه بصورت تصادفی به هر انتخاب اختصاص یافته اند. بنابراین جهت جستجو در الگوریتم ژنتیک چند هدفی ما ثابت نیست. تعداد مشخصی از افراد در این مجموعه به نسل بعدی که افراد نابغه هستند، مواردی به ارث می دهند. برای نشان دادن اینکه روش ما می تواند مسائل بهینه سازی چند هدفی را با دیدهای پیشروی Pareto کاو کنترل نماید ما الگوریتم ژنتیک پیشنهادی خود را به مسأله بهینه سازی تابع دو هدفی با دیدهای Pareto ی کاو اعمال می کنیم. عملکرد الگوریتم ژنتیک چند هدفی ما با اعمال آن به مسأله زمانبندی flowshop با دو هدف آزموده است: برای به حداقل رساندن زمان اتمام آخرین کار و به حداقل رساندن تأخیر کل. علاوه بر این ما الگوریتم خود را به مسأله زمانبندی flowshop با سه هدف اعمال کرده ایم: برای به حداقل رساندن زمان اتمام آخرین کار، به حداقل رساندن تأخیر مجموع، و برای به حداقل رساندن flowtime مجموع. |
بخشی از مقاله انگلیسی |
Abstract ln this paper, we propose a multi-objective genetic algorithm and apply it to flowshop scheduling. The characteristic features of our algorithm are its selection procedure and elite preserve strategy. The selection procedure in our multi-objective genetic algorithm selects individuals for a crossover operation based on a weighted sum of multiple objective functions with variable weights. The elite preserve strategy in our algorithm uses multiple elite solutions instead of a single elite solution. That is, a certain number of individuals are selected from a tentative set of Pareto optimal solutions and inherited to the next generation as elite individuals. In order to show that our approach can handle multi-objective optimization problems with concave Pareto fronts, we apply the proposed genetic algorithm to a two-objective function optimization problem with a concave Pareto front. Last, the performance of our multi-objective genetic algorithm is examined by applying it to the flowshop scheduling problem with two objectives: to minimize the makespan and to minimize the total tardiness. We also apply our algorithm to the flowshop scheduling problem with three objectives: to minimize the makespan, to minimize the total tardiness, and to minimize the total flowtime. ۱ Introduction Flowshop scheduling problems are one of the most well known problems in the area of scheduling. The objective of minimizing the makespan is often employed as a criterion of flowshop scheduling since Johnson’s work [1]. Various heuristic approaches (e.g., Dannenbring [2], Nawaz et al. [3], Osman and Potts [4] and Widmer and Hertz [5]) as well as optimization techniques (e.g., Ignall and Schrage [6] and Lomnicki [7]) have been proposed for minimizing the makespan. While these studies treated a single objective, many real-world problems involve multiple objectives. Recently several researchers have tackled multi-objective flowshop scheduling problems. For example, Ho and Chan [8] proposed a heuristic method for flowshop scheduling with bicriteria, Gangadharan et al. [9] proposed a simulated annealing heuristic for flowshop scheduling with bicriteria, and Morizawa et al. [10] proposed a complex random sampling method for multi-objective problems. Genetic algorithms have been mainly applied to single-objective optimization problems. When we apply a single-objective genetic algorithm to a multi-objective optimization problem, multiple objective functions should be combined into a scalar fitness function. If we assign a constant weight to each of the multiple objective functions for combining them, the direction of search in the genetic algorithm is constant in the multi-dimensional objective space as shown in Fig. 1. In Fig. I, f~(.) is an objective function to be maximized and J~(.) is to be minimized. The closed circle in Fig. 1 represents the final solution by the single-objective genetic algorithm. Some studies have been attempted for designing multi-objective genetic algorithms since Schaffer’s work [11]. Schaffer proposed the Vector Evaluated Genetic Algorithm (VEGA) for finding Pareto optimal solutions of multi-objective optimization problems. In Schaffer’s VEGA, a population was divided into disjoint subpopulations, then each subpopulation was governed by its own objective function. Although Schaffer [11] reported some successful results, his approach seems to be able to find only extreme solutions on Pareto fronts as shown in Fig. 2 because its search directions are parallel to the axes of the objective space. Schaffer suggested two approaches to improve his approach in his paper [11]. One is to provide a heuristic selection preference for non-dominated individuals in each generation. The other is to crossbreed among the “species” by adding some mate selection. The point of multi-objective optimization problems is how to find all possible tradeoffs among multiple objective functions that are usually conflicting. Since it is difficult to choose a single solution for a multi-objective optimization problem without iterative interaction with the decision maker, one general approach is to show the set of Pareto optimal solutions to the decision maker. Then the decision maker can choose any one of the Pareto optimal solutions. To find out all the Pareto optimal solutions by genetic algorithms, the variety of individuals should be kept in each generation. Recently Gen et al. [12] proposed a genetic algorithm for solving a bicriteria transportation problem, Tamaki et al. [13] proposed a genetic algorithm for scheduling problems with multi-criteria, and Horn et al. [14] proposed the Niched Pareto Genetic Algorithm by incorporating the concept of Pareto domination in the selection procedure and applying a niching pressure to spend the population out along Pareto fronts. In this paper, we propose a multi-objective genetic algorithm with various search directions as shown in Fig. 3. There are two characteristic features of our algorithm. One is its selection procedure. In the selection procedure, our multi-objective genetic algorithm uses a weighted sum of multiple objective functions to combine them into a scalar fitness function. The weights attached to the multiple objective functions are not constant but randomly specified for each selection. Therefore the direction of the search in our multi-objective genetic algorithm is not constant. The other characteristic feature of our algorithm is its elite preserve strategy. A tentative set of Pareto optimal solutions is preserved in the execution of our multi-objective genetic algorithm. A certain number of individuals in this set are inherited to the next generation as elite individuals. In order to show that our approach can handle multi-objective optimization problems with concave Pareto fronts, we apply our proposed genetic algorithm to a two-objective function optimization problem with concave Pareto fronts. The performance of our multi-objective genetic algorithm is examined by applying it to the flowshop scheduling problem with two objectives: to minimize the makespan and to minimize the total tardiness. We also apply our algorithm to the flowshop scheduling problem with three objectives: to minimize the makespan, to minimize the total tardiness, and to minimize the total flowtime. |