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

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

يک الگوريتم تکاملي کوانتومي با عملگر به روزرساني مقيد براي حل مسايل بهينه سازي ترکيبياتي

چکيده : در اين مقاله ، يک الگوريتم تکاملي کوانتومي بـه نـام NQEA پيشنهاد مي شود. در الگوريتم پيشنهادي ، به منظـور افـزايش کـارآيي از يک عملگر به روزرساني جديد استفاده يشود. در ايـن عملگـر، هنگـام به روزرساني هر يک از افراد جمعيت از مشارکت بهترين جواب بدسـت آمده توسط آن فرد در نسل هاي قبلي و بهترين جواب بـه دسـت آمـده توسط ساير افراد جمعيت در نسل جاري استفاده مي شود. همچنـين ، بـا اعمال محدوديت بر روي مقادير بيت هاي کوانتومي از همگرايـي زودرس آنها جلوگيري به عمل مي آيـد. عملکـرد الگـوريتم NQEA بـا عملکـرد الگوريتم ژنتيـک اسـتاندارد CGA و الگـوريتم هـاي تکـاملي کوانتـومي QEA و VQEA مقايسه مي شود. با تحليل رفتار الگو يتم NQEA بـر روي مسأله OneMax مشخص شود که اين الگـو يتم بهينـه سـازي برخلاف الگوريتم QEA داراي مشکل همگرايي زودرس (ناشي از پديده سواري مجاني ) نمي باشد. با ارزيابي کـارآيي الگـوريتم NQEA بـر روي مسأله بهينه سازي ترکيبياتي شناخته شده NK-landscapes مـشخص می شود که در اين الگوريتم بهينه سازي نسبت به الگوريتم هـاي CGA، QEA و VQEA توازن بهتري ميان توانايي هاي کـاوش و بهـره بـرداري الگوريتم برقرار می شـود. همچنـين ، الگـوريتم NQEA در مقايـسه بـا الگوريتم هاي فوق از کارآيي و سرعت همگرايي بالاتري برخوردار است .

١- مقدمه
محاسبات کوانتومي ١ در اوايل دهـه ١٩٨٠ مـيلادي توسـط Benioff و Feynman مطرح شده است . در محاسبات کوانتومي مفاهيمي از قبيـل کامپيوترهاي کوانتومي و الگوريتم هاي کوانتومي مـورد توجـه محققـين قرار دارد [١]. در سال هاي اخيـر رشـد ف اينـده اي در زمينـه تحقيقـات مربوط به تئو ي و طراحي الگوريتم ها و کامپيوترهـاي انتـومي انجـام شده است . اين تح يقات به منظور دستيابي به قدرت محاسـباتي بـالاتر در مقايــسه بــا کامپيوترهــاي معمــولي صــورت گرفتــه انــد. همچنــين ، تلاش هاي زيادي در زمينه اسـتفاده از محاسـبات تکـاملي (بـراي مثـال برنامه نويسي ژنتيـک ) بـراي توليـد مـدارهاي مـورد نيـاز کامپيوترهـاي کوانتومي صورت گرفته است [٢]. يـک زمينـه تحقيقـاتي جالـب توجـه ديگر، استفاده از مفاهيم محاسبات کوانتومي به عنوان منبع الهـام بـراي طراحي الگوريتم هاي قابل اجرا بر روي کامپيوترهاي معمـولي اسـت . در اين زمينه ، تلاش محققان بر روي ترکيب مفـاهيم محاسـبات کوانتـومي مانند موج هاي ايستاده ، تـداخل ، بيـت هـاي کوانتـومي ٢، درهـم تنيـدگي کوانتومي ٣ و برهم نهشتي خطي حالات ٤ با مفاهيم محاسبات تکاملي [٣- ٨] متمرکز مي باشد.
استفاده از مفاهيم محاسبات کوانتومي براي افزايش کارآيي اجـراي الگوريتم هاي تکاملي بـر روي کامپيوترهـاي معمـولي منجـر بـه توسـعه الگوريتم هاي تکاملي کوانتومي (QEAs٥) شده است . Han و Kim [٤]
الگوريتم تکـاملي کوانتـومي QEA را بـراي حـل مـسايل بهينـه سـازي ترکيبياتي پيشنهاد کرده انـد. در الگـوريتم QEA از مفـاهيم محاسـبات کوانتومي از قبيل بيت کوانتومي ، بـرهم نهـشتي خطـي حـالات و گيـت چرخشي کوانتومي ٦ استفاده مـي شـود و در آن بـراي اولـين بـار امکـان استفاده از نمايش کوانتومي به جاي نمايش هاي متداول دودويي ، عد ي و نمادي مطرح شده است . به همين دليل مفاهيم استفاده شده در ايـن الگوريتم تکاملي کوانتومي زيربنـاي بـسياري از الگـوريتم هـاي تکـاملي کوانتومي موجود را تشکيل مي دهد. Platel و همکارانش [٧] به بررسي نقاط ضعف الگوريتم QEA پرداخته اند و مشکل همگرايي زودرس را در اين الگو يتم تشخيص داده اند. آنها براي رفع ايـن مـشکل کـه ناشـي از پديده سواري مجـاني ٧ اسـت ، الگـوريتم تکـاملي کوانتـومي VQEA را پيشنهاد کرده اند. يک مزيت ذکر شده براي الگوريتم VQEA آن اسـت که اطلاعات به دسـت آمـده در مـورد فـضاي جـستجو در طـي تکامـل جمعيت در سطح يک فرد باقي نمـي مانـد و بـين اعـضاي جمعيـت بـه اشتراک گذاشته مي شود.
از الگـوريتم هـاي تکـاملي کوانتـومي در حـل مـسايل بهينـه سـازي ترکيبياتي [٤، ٥، ٧، ٨]، بهينـه سـازي عـددي [٩، ١٠] و حـل مـس يل دنياي واقعـي ماننـد تخـصيص ديـسک [١١]، تـش يص چهـره [١٢] و پردازش سيگنال [١٣] استفاده شده است .
در اين مقاله ، يک الگوريتم تکاملي کوانتومي جديد به نام NQEA پيشنهاد مي شود. در الگوريتم پيـشنهادي ، از يـک عملگـر انـدازه گيـري

چندگانه و يک عملگر به روزرساني مقيد استفاده مي شود. بـراي بررسـي عملکرد الگوريتم NQEA، ابتدا رفتار بهينه سازي اين الگوريتم بـر روي مسأله OneMax مـورد تحليـل قـرار مـي گيـرد. سـپس ، کـارآيي ايـن الگوريتم با کارآيي الگوريتم هاي CGA،QEA [٤] و VQEA [٧] براي حل مسأله بهينه سازي ترکيبياتي NK-landscapes مقايسه مي شود.
در ادامه ، در بخش ٢ مفاهيم اصلي مورد استفاده در الگـوريتم هـاي تکاملي کوانتومي شرح داده مـي شـوند. در بخـش ٣، الگـوريتم تکـاملي کوانتومي NQEA معرفي مي شود و رفتـار بهينـه سـازي ايـن الگـوريتم مورد تحليل قرار ميگيرد. در بخش ٤ نتايج آزمايشات انجام شده بـراي ارزيــابي کــارآيي NQEA ارائــه مــي شــود و در نهايــت در بخــش ٥ نتيجه گيري به عمل مي آيد.

٢- الگوريتم هاي تکاملي کوانتومي
زيربناي الگـوريتم هـاي تکـاملي کوانتـومي بـر پايـه مفـا يم محاسـبات کوانتومي از قبيل بيت کوانتومي ، بـرهم نهـشتي خطـي حـالات و گيـت کوانتومي استوار است .
بيت کوانتومي : بيت کوانتومي يا کيوبيت به عنـوان کـوچکترين واحـد ذخيره سازي اطلاعات تعريف مي شود که مي تواند در حالت ، حالـت ”١“ يا يک برهم نهشتي خطي از هر دو حالت قرارگيرد. هر کيوبيت بـا يـک زوج از مقـادير ( ) تعريـف مـي شـود. مربـع مقـادير  و  احتمـال دو حالـت ”٠“ و ”١“ را نمـايش مـي دهنـد. بنـابراين ، هنگـام اندازه گيري ٩ يک کيوبيت احتمال توليد حالت ”٠“ برابر و احتمـال توليد حالت ”١“ برابر است .

فرد کيوبيتي : فرد کيوبيتي به صورت رشـته اي از کيوبيـت هـا تعريـف مي شود. هر فرد کيوبيتي به دليل دارا بودن نمايش احتم لي قادر اسـت يک برهم نهشتي خطي از حالات (جواب هاي بالقوه ) را نمايش دهـد. بـه بيان ديگر، هر فرد کيوبيتي با m کيوبيت مي تواند حالت را به طور همزمان نمايش دهد. به عنوان مثال ، فرد کيوبيتي زير با سه کيوبيـت را در نظر بگيريد:

فرد کيوبيتي فوق قادر است هشت حالت ”٠٠٠“، ”٠٠١“، ”٠١٠“، ”٠١١“، ”١٠٠“، ”١٠١“، ”١١٠“ و ”١١١“ را به ترتيـب بـا احتمـالات نمـايش دهـد. هـر فـرد کيوبيتي به عنوان یک توزيع از همه جواب هاي بالقوه در فضاي جستجو در نظر گرفته می شود. مزيت نمايش کيوبيتي نسبت به ساير نمـايش هـا از قبيل نمايش دودويي ، عدد ي و نمادي آن اسـت کـه مـي توانـد تنـوع شتري را در جمعيت فراهم کند.

گيت کوانتومي : در الگوريتم هاي تکاملي کوانتومي بـراي بـه روزرسـاني مقادير کيوبيت ها از يک گيت کوانتومي استفاده مي شود. اعمـال عملگـر گيـت کوانتـومي بــر روي هـر کيوبيـت ف آينــد تکامـل را در جمعيــت شبيه سازي مي کند. مقادير هر کيوبيت پس از به روزرساني توسط گيـت کوانتومي بايد در رابطه زير صدق کنند:

که مقادير کيوبيت پس از به روزرساني هستند. در اين مقالـه ، براي به روزرساني مقادير کيوبيـت هـا از گيـت چرخـشي کوانتـومي [٤] استفاده مي شود:

که  زاويه چرخش هر يک از کيوبيت هـا بـه سـمت حالـت ”٠“ يـا حالت ”١“ است .

٣- الگوريتم تکاملي کوانتومي NQEA
در اين بخش ، يک الگوريتم تکاملي کوانتومي به نام NQEA براي حـل مسايل بهينه سازي ترکيبياتي ارائه مـي شـود. در ايـن الگـو يتم تکـاملي کوانتومي ، ابتدا يک جمعيت اوليه از افراد کيوبيتي توليد مـي شـود. هـر فرد کيوبيتي همه جواب هـاي بـالقوه در فـضاي جـستجو را بـه صـورت احتمالي نمايش مي دهد. سپس ، در هر نـسل عملگرهـاي کوانتـومي بـر روي هر يک از افراد کيوبيتي اعمال مي شوند تـا نـسل بعـدي جمعيـت توليد شود.

٣-١ ساختار الگوريتم
فرض کنيد يک جمعيت از افراد کيوبيتي در نسل t باشد:

که n اندازه جمعيت است . هر فرد کيوبيتي از يک رشته از کيوبيت ها به طول m تشکيل مي شود:

در اين فرد کيوبيتي ، هـر کيوبيـت بـا يـک زوج از مقـادير نمايش داده مي شود:

متنـاظر بـا فـرد کيـوبيتي ، دو رشـته دودويـي بـه نـام هـاي اندازه گيري جاري و بهترين اندازه گيري شخصي نگهـداري مي شود. رشته دودويي با اندازه گيري فرد کيوبيتي در نسل جاري توليد مي شود. رشته دودويي بهترين اندازه گيـري حاصـل از فـرد کيوبيتي تا نسل جاري را نمايش مي دهد.
در هر نسل t، ابتدا يک عملگر اندازه گيري چندگانه بر روي هر فرد کيوبيتي اعمال مي شود تا اندازه گيري جـاري توليـد شـود.

سپس ، با توجه به بهترين اندازه گيري شخصي به روزرساني مي شود. سرانجام ، از بين اندازه گيري هاي جاري افراد کيـوبيتي بهتـرين آنها انتخاب شده و بـا نمـايش داده مـي شـود. همچنـين ، از بـين بهترين اندازه گيري هاي شخصي افراد کيوبيتي بهترين آنها انتخاب شـده و با (t)bˆ نمايش داده مي شود. (t)cˆ بهترين اندازه گيري نسل جـاري و
(t)bˆ بهترين اندازه گيري سراسري ناميده مي شود. در نهايت ، بـا اعمـال عملگـر بـه روزرسـاني مقيـد بـر روي هـر فـرد کيـوبيتي (t)qi مقـادير کيوبيت هاي آن فرد به روزرساني مي شوند. مراحل فوق تکرار مي شوند تـا هنگامي که يکي از شرايط خاتمه يافتن الگوريتم (از قبيل حداکثر تعداد دفعات توليد نسل tmax ) برآورده شود. در نهايت ، بهترين انـدازه گيـري سراسري (t)bˆ به عنوان جواب نهايي الگوريتم برگردانده مي شود.

procedure NQEA
٠ پ t
1. Initialize population Q(t)
while (not termination condition) do
1+t پ t
2 forApapclyh tQh-ebitmunltdii-vmideuaaslurqei (mt)entdooperator to q (t)
i
in order to form the current measurement ci (t)
and update the personal best measurement bi (t)
end for
3. Calculate the generation best measurement cˆ(t)
4. Calculate the global best measurement bˆ(t)
for each Q-bit individual do
qi (t)
5. Apply the restricted update operator to qi (t)
endnwdhfioler
end procedure
شکل ١: شبه کد الگوريتم NQEA
در شکل ١ شبه کد الگوريتم NQEA نمايش داده شـده اسـت . در
ادامه ، مراحل اجراي الگوريتم فوق شرح داده مي شوند:
١. در ابتداي اجراي الگوريتم ، يک جمعيت اوليه از افراد کيوبيتي توليـد شود. بدين منظور، مقا ير همه کيوبيت هاي هر فرد کيـوبيتي (٠) q
مي i
برابر مقدار يکسان ١ قرار داده مي شود.


که n,...,1,2i و m,...,1,2j است . مقداردهي اوليه فوق بـه ايـن معني است که هر فرد کيوبيتي (٠) يک برهم نهشتي خطـي از تمـام
qi
حالات ممکن (جواب هاي بالقوه ) در فضاي جستجو را با احتمال يکـسان ن٢م.ايدرش ايمن يمدرهحدل.ه ، عملگر اندازه گيري چندگانه بر روي هر فـرد کيـوبيتي
(t)qi اعمال مي شود. در ايـن عملگـر، ابتـدا (t)qi بـه تعـداد l٠ بـار اندازه گيري مي شود. با هر بار اندازه گيري همه کيوبيت هـاي (t)qi يـک رشته دودويي توليد مي شود. هنگام انـدازه گيـري هـر کيوبيـت (qi j)t
,
براساس مقادير (ai j) و (bi j) عدد صفر يا يـک توليـد مـي شـود.
, ,
سپس ، از بين اندازه گيري هاي ب دسـت آمـده بهتـرين آنهـا بـه عنـوان اندازه گيري جاري (ci)t انتخاب مي شود. در نهايت ، بهترين اندازه گيري
شخصي (t)bi با توجه به اندازه گيري جاري (t)ci به روزرساني مي شود:

که f تابع برازندگي است .
٣. در اين مرحله ، از بين اندازه گيري هاي جاري افـراد کيـوبيتي بهتـرين
آنها به عنوان بهترين اندازه گيري نسل جاري (t)cˆ انتخاب مي شود:

٤. در اين مرحله ، از بين بهترين اندازه گيري هاي شخصي افراد کيـوبيتي بهترين آنهـا بـه عنـوان بهتـرين انـدازه گيـري سراسـري (t)bˆ انتخـاب
مي شود:

٥. در اين مرحله ، عملگر به روزرساني مقيـد بـر روي هـر فـرد کيـوبيتي
(t)qi اعمال مي شود. در اين عملگر، ابتدا با استفاده از گيـت چرخـ ي کوانتومي مقادير هر کيوبيت (qi j)t به روزرساني مـي شـود. سـپس ، بـا
,
اعمال قدرمطلق بر روي مقادير به روزرساني شده ، محـدوده چـرخش آن
کيوبيت تنها به ربع اول مثلثاتي محدود مي شود:

, , ,
که (Dqi j زاويه چرخش (qi j)t به سمت حالت ”٠“ يا حالت ”١“
, ,
است . در شکل ٢ محدوده چرخش کيوبيت (qi j)t نمـايش داده شـده
,
است .
گيت چرخشي کوانتومي باعث نزديک شدن هر کيوبيـت بـه حالـت
”٠“ يا حالت ”١“ مي شود. در صـورت همگـرا شـدن يـک کيوبيـت بـه حالت ”٠“ يا حالت ”١“، نمايش احتمالي آن کيوبيـت از بـين مـي رود.
بنابراين ، کيوبيت فوق قـادر نخواهـد بـود بـا اتکـا بـه خـود از وضـعيت همگرايي که به آن دچار شده فرار کند. در الگوريتم NQEA بـا اعمـال محدوديت زير بر روي مقادير به روزرساني شده کيوبيـت هـا از همگرايـي
زودرس آنها جلوگيري به عمل مي آيد:
اگر ٠»(١ ai, j) باشد: