سامانه مدیریت همایش های علمی


یازدهمین کنفرانس بین‌المللی مهندسی صنایع


عنوان فارسی	تحلیل فضای جواب مساله بسته بندی مجموعه (Set Packing) و حل آن به کمک الگوریتم ژنتیک و ازدحام ذرات باینری

چکیده فارسی مقاله	ساله بسته بندی مجموعه شامل انتخاب زیر مجموعه های یک مجموعه مرجع از میان لیستی از زیر مجموعه های آن می باشد به گونه ای که زیر مجموعه های منتخب دوبه دو گسسته باشند. این مسأله از جمله مسایل آن پی سخت است که در زمان چند جمله ای قابل حل نیست. بنابراین به منظور یافتن جوابهای خوب ولی نه لزوما بهینه برای این گونه مسایل، از روش های فراابتکاری استفاده می شود، با این حال، در مقالات موجود بر روی این مسأله، هیچگاه توجیه علمی و قابل قبولی برای دلیل انتخاب روشهای فراابتکاری بکار گرفته شده ارائه نشده است. در مقاله حاضر به تجزیه و تحلیل فضای جوابه مسأله بسته بندی مجموعه پرداخته شده و بر مبنای نتایج این تحلیل یک الگوریتم فرا ابتکاری مناسب جهت حل مساله انتخاب و اجرا شده است. بدین منظور ابتدا مسأله با روش الگوریتم جستجوی محلی حل شده است و نتایج حاصله برای یافتن مقادیر معیارهای آماری و سپس تحلیل قضای جواب مورد استفاده قرار گرفته است. نتایج حاصل از این تحلیل، استفاده از قرابتکاری های مبتنی بر جمعیت را توصیه می کند، که بر اساس آن الگوریتم های ژنتیک و ازدحام ذرات باینری برای حل مساله توسعه یافته شده است. نتایج محاسباتی نشان دادند که الگوریتم ژنتیک با صرف مدت زمان کمتر و ارائه جوابی با کیفیت بهتر نسبت به الگوریتم ازدحام ذرات باینری، برای این مساله مناسبتر است

کلیدواژه‌های فارسی مقاله	تحلیل فضای جواب، الگوریتم جستجوی محلی، الگوریتم ژنتیک، الگوریتم ازدحام ذرات باینری

عنوان انگلیسی	Fitness Landscape Analysis of the Set Packing Problem and its Solution by GA and PSO Metaheuristics

چکیده انگلیسی مقاله	The Set Packing Problem (SPP) concerns with selecting a number of subsets among a given set of subsets of a reference set such that they are mutually disjoint. SPP is an NP-hard problem that cannot be solved in polynomial time. Therefore, in order to find good (and not necessarily optimal) solutions, metaheuristic methods are frequently used. However, in no previous work a reliable justification has been presented for using certain metaheuristics. In this paper, landscape analysis of the solution space of the SPP is conducted for the first time, based on which an appropriate metaheuristics is selected and implemented. For this purpose, local search algorithm is employed for calculating some statistical criteria and analyzing the solution space, which prescribe using population-based metaheuristics for this problem. As a result, the Genetic and Binary Particle Swarm Optimization (BPSO) algorithms were developed. Computational results showed that the GA presents better solutions in less time than the BPSO, which testify that it is more appropriate for solving the Set Packing Problem.

کلیدواژه‌های انگلیسی مقاله	Set packing problem, Landscape analysis, Local search algorithm, Genetic algorithm, Particle Swarm Optimization

نویسندگان مقاله	فرنيا ضروري \| Farnia Zarouri Tarbiat Modares University دانشگاه تربیت مدرس تهران اليپس مسيحي \| Ellips Masehian Tarbiat Modares University دانشگاه تربیت مدرس تهران سيد حسام الدين ذگردي \| Seyed Hesameddin Zegordi Tarbiat Modares University دانشگاه تربیت مدرس تهران

نشانی اینترنتی	iiec2015.org
فایل مقاله	دریافت فایل مقاله
کد مقاله (doi)
زبان مقاله منتشر شده	fa
موضوعات مقاله منتشر شده
نوع مقاله منتشر شده

برگشت به: صفحه اول پایگاه \| دوره مرتبط \| کنفرانس مرتبط \| فهرست کنفرانس ها