سال انتشار: ۱۳۸۷

محل انتشار: دومین کنگره مشترک سیستم های فازی و سیستم های هوشمند

تعداد صفحات: ۷

نویسنده(ها):

مهرشاد خسرویانی – ایران، تهران، خیابان حافظ، ۴۲۴ ، دانشگاه صنعتی امیرکبیر، دانشکده مهندس
قاسم محمدی –
سعادت پورمظفری –

چکیده:

یکی از مسائل ترکیبی پرکاربردNPدر علوم محض و مهندسی بشمار میرود. روشن است که برای حل این قبیل مسائل ویافتن پاسخ بهینه آنها، هیچگونه الگوریتمی با پیچیدگی زمانی چندجملهای وجود ندارد. از اینرو، در طی سالیان مختلف، روشهای حلمکاشفهای بسیاری برای حل آنها ارائه شده و توسعه یافتهاند. در این مقاله، با تکیه بر مفاهیم محاسبات کوانتومی، مانند کیوبیتها و برهمنهی حالات کیوبیتی، در کنار اصول اولیه الگوریتمهای ژنتیکی، از قبیل کروموزومها و جمعیتی متشکل از آنها، یک الگوریتم مکاشفهای افراز ۳ – بخشی پیشنهاد میگردد. سپس، برای تعیین میزان کارایی الگوریتم مذکور، به مقایسه نتایج آن با الگوریتم ژنتیکیبدونِ عملگر ترکیب میپردازیم. نتایج تجربی حاصل از اعمال این دو الگوریتم بر روی گرافهای محک نشان میدهد که الگوریتم ژنتیکی کوانتومی میتواند تا ۱۰ % عملکرد بهتری را نسبت به الگوریتم دیگر مورد بحث در مسئله افراز ۳ – بخشی گرافها داشته باشد