خوارزمية التحسين الحلزوني

الموسوعة الحرة
يشترك الشكل الحلزوني في السلوك العالمي (الأزرق) والسلوك المكثف (الأحمر).

في الرياضيات، تعتبر خوارزمية التحسين الحلزوني (SPO) خوارزمية استكشافية مستوحاة من الظواهر الحلزونية في الطبيعة.

طُرحت خوارزمية SPO الأولى لتحسين ثنائي الأبعاد غير المقيد [ 1 ] استنادًا إلى نماذج حلزونية ثنائية الأبعاد. وتم توسيع نطاقها لتشمل مسائل متعددة الأبعاد (n-dimensional) بتعميم النموذج الحلزوني ثنائي الأبعاد إلى نموذج حلزوني متعدد الأبعاد (n-dimensional) [ 2 ] . توجد إعدادات فعّالة لخوارزمية SPO، منها إعداد اتجاه الانحدار الدوري [ 3 ] وإعداد التقارب [ 4 ] .

استعارة

كان الدافع وراء التركيز على الظواهر الحلزونية نابعًا من إدراك أن الديناميكيات التي تولد الحلزونات اللوغاريتمية تشترك في سلوك التنويع والتكثيف. يمكن لسلوك التنويع أن يخدم البحث الشامل (الاستكشاف)، بينما يُمكّن سلوك التكثيف من إجراء بحث مكثف حول حل جيد تم التوصل إليه (الاستغلال).

الخوارزمية

خوارزمية التحسين الحلزوني (SPO)

خوارزمية SPO هي خوارزمية بحث متعددة النقاط لا تعتمد على تدرج دالة الهدف ، وتستخدم نماذج حلزونية متعددة يمكن وصفها بأنها أنظمة ديناميكية حتمية. وبما أن نقاط البحث تتبع مسارات حلزونية لوغاريتمية باتجاه المركز المشترك، المحدد بأنه أفضل نقطة حالية، فإنه يمكن إيجاد حلول أفضل وتحديث المركز المشترك.

خوارزمية SPO العامة لحل مشكلة التصغير في ظل الحد الأقصى للتكراركالأعلى{\displaystyle k_{\max }}(معيار الإنهاء) هو كما يلي:

0) حدد عدد نقاط البحثم≥2{\displaystyle m\geq 2}والحد الأقصى لعدد التكراراتكالأعلى{\displaystyle k_{\max }}. 1) ضع نقاط البحث الأوليةxأنا(0)∈Rن (أنا=1،...،م){\displaystyle x_{i}(0)\in \mathbb {R} ^{n}~(i=1,\ldots ,m)}وتحديد المركزx⋆(0)=xأناب(0){\displaystyle x^{\star }(0)=x_{i_{\text{b}}}(0)}،أناب=أرجينينأنا=1،...،م⁡{و(xأنا(0))}{\displaystyle \displaystyle i_{\text{b}}=\mathop {\text{argmin}} _{i=1,\ldots ,m}\{f(x_{i}(0))\}}ثم اضبطك=0{\displaystyle k=0}. 2) حدد معدل الخطواتر(ك){\displaystyle r(k)}بحسب القاعدة. 3) تحديث نقاط البحث:xأنا(ك+1)=x⋆(ك)+ر(ك)R(θ)(xأنا(ك)-x⋆(ك))(أنا=1،...،م).{\displaystyle x_{i}(k+1)=x^{\star }(k)+r(k)R(\theta )(x_{i}(k)-x^{\star }(k))\quad (i=1,\ldots ,m).} 4) تحديث المركز:x⋆(ك+1)={xأناب(ك+1)(لو و(xأناب(ك+1))<و(x⋆(ك)))،x⋆(ك)(خلاف ذلك)،{\displaystyle x^{\star }(k+1)={\begin{cases}x_{i_{\text{b}}}(k+1)&{\big (}{\text{if }}f(x_{i_{\text{b}}}(k+1))<f(x^{\star }(k)){\big )},\\x^{\star }(k)&{\big (}{\text{otherwise}}{\big )},\end{cases}}}أينأناب=أرجينينأنا=1،...،م⁡{و(xأنا(ك+1))}{\displaystyle \displaystyle i_{\text{b}}=\mathop {\text{argmin}} _{i=1,\ldots ,m}\{f(x_{i}(k+1))\}}. 5) اضبطك:=ك+1{\displaystyle k:=k+1}. لوك=كالأعلى{\displaystyle k=k_{\max }}إذا تم استيفاء الشروط، فقم بالإنهاء والإخراج.x⋆(ك){\displaystyle x^{\star }(k)}وإلا، فارجع إلى الخطوة 2).

جلسة

يعتمد أداء البحث على ضبط مصفوفة الدوران المركبةR(θ){\displaystyle R(\theta )}معدل الخطواتر(ك){\displaystyle r(k)}والنقاط الأوليةxأنا(0) (أنا=1،...،م){\displaystyle x_{i}(0)~(i=1,\ldots ,m)}الإعدادات التالية جديدة وفعالة.

الإعداد 1 (إعداد اتجاه الهبوط الدوري)

يُعد هذا الإعداد إعدادًا فعالًا للمسائل ذات الأبعاد العالية في ظل الحد الأقصى للتكراراتكالأعلى{\displaystyle k_{\max }}الشروط المتعلقة بـR(θ){\displaystyle R(\theta )}وxأنا(0) (أنا=1،...،م){\displaystyle x_{i}(0)~(i=1,\ldots ,m)}تضمن هذه النماذج مجتمعةً توليد اتجاهات هبوط دورية. حالةر(ك){\displaystyle r(k)}يعمل على الاستفادة من اتجاهات الهبوط الدورية في ظل إنهاء البحثكالأعلى{\displaystyle k_{\max }}.

  • تعيينR(θ){\displaystyle R(\theta )}على النحو التالي:R(θ)=[0ن-1⊤-1أنان-10ن-1]{\displaystyle R(\theta )={\begin{bmatrix}0_{n-1}^{\top }&-1\\I_{n-1}&0_{n-1}\\\end{bmatrix}}}أينأنان-1{\displaystyle I_{n-1}}هو(ن-1)×(ن-1){\displaystyle (n-1)\times (n-1)}مصفوفة الهوية و0ن-1{\displaystyle 0_{n-1}}هو(ن-1)×1{\displaystyle (n-1)\times 1}متجه صفري.
  • ضع النقاط الأوليةxأنا(0)∈Rن{\displaystyle x_{i}(0)\in \mathbb {R} ^{n}}(أنا=1،...،م){\displaystyle (i=1,\ldots ,m)}بشكل عشوائي لتحقيق الشرط التالي:

مينأنا=1،...،م{الأعلىج=1،...،م{رتبة[دج،أنا(0) R(θ)دج،أنا(0)  ⋯  R(θ)2ن-1دج،أنا(0)]}}=ن{\displaystyle \min _{i=1,\ldots ,m}\{\max _{j=1,\ldots ,m}{\bigl \{}{\text{rank}}{\bigl [}d_{j,i}(0)~R(\theta )d_{j,i}(0)~~\cdots ~~R(\theta )^{2n-1}d_{j,i}(0){\bigr ]}{\bigr \}}{\bigr \}}=n} أيندج،أنا(0)=xج(0)-xأنا(0){\displaystyle d_{j,i}(0)=x_{j}(0)-x_{i}(0)}لاحظ أن هذا الشرط يتم تحقيقه بالكامل تقريبًا عن طريق وضع عشوائي، وبالتالي فإن عدم إجراء أي فحص أمر جيد في الواقع.

  • تعيينر(ك){\displaystyle r(k)}في الخطوة الثانية) كما يلي:ر(ك)=ر=دلتاكالأعلى    (قيمة ثابتة){\displaystyle r(k)=r={\sqrt[{k_{\max }}]{\delta }}~~~~{\text{(قيمة ثابتة)}}}حيث يكون صغيرًا بما فيه الكفايةدلتا>0{\displaystyle \delta >0}مثلدلتا=1/كالأعلى{\displaystyle \delta =1/k_{\max }}أودلتا=10-3{\displaystyle \delta =10^{-3}}[ 3 ]​

الإعداد 2 (إعداد التقارب)

يضمن هذا الإعداد تقارب خوارزمية SPO إلى نقطة ثابتة في ظل الحد الأقصى للتكراراتكالأعلى=∞{\displaystyle k_{\max }=\infty }إعداداتR(θ){\displaystyle R(\theta )}والنقاط الأوليةxأنا(0) (أنا=1،...،م){\displaystyle x_{i}(0)~(i=1,\ldots ,m)}وهي نفسها الإعدادات المذكورة أعلاه (الإعداد 1). إعدادر(ك){\displaystyle r(k)}وهو كما يلي.

  • تعيينر(ك){\displaystyle r(k)}في الخطوة الثانية) كما يلي:ر(ك)={1(ك⋆≦ك≦ك⋆+2ن-1)،ح(ك≧ك⋆+2ن)،{\displaystyle r(k)={\begin{cases}1&(k^{\star }\leqq k\leqq k^{\star }+2n-1),\\h&(k\geqq k^{\star }+2n),\end{cases}}}أينك⋆{\displaystyle k^{\star }}(وهي عملية تكرار يتم فيها تحديث المركز حديثًا في الخطوة 4) وح=دلتا2ن،دلتا∈(0،1){\displaystyle h={\sqrt[{2n}]{\delta }},\delta \in (0,1)}مثلدلتا=0.5{\displaystyle \delta =0.5}لذا، علينا إضافة القواعد التالية بشأنك⋆{\displaystyle k^{\star }}إلى الخوارزمية:
•(الخطوة 1)ك⋆=0{\displaystyle k^{\star }=0}.
•(الخطوة 4) إذاx⋆(ك+1)≠x⋆(ك){\displaystyle x^{\star }(k+1)\neq x^{\star }(k)}ثمك⋆=ك+1{\displaystyle k^{\star }=k+1}[ 4 ]​

الأعمال المستقبلية

  • تُعتبر الخوارزميات ذات الإعدادات المذكورة أعلاه حتمية . لذا، فإن دمج بعض العمليات العشوائية يجعل هذه الخوارزمية فعّالة في التحسين الشامل . وقد أثبت كروز-دوارته وآخرون [ 5 ] ذلك من خلال تضمين اضطرابات عشوائية في مسارات البحث الحلزونية. ومع ذلك، لا يزال هذا المجال مفتوحًا لمزيد من الدراسات.
  • لإيجاد توازن مناسب بين دوامات التنويع والتكثيف اعتمادًا على فئة المشكلة المستهدفة (بما في ذلككالأعلى{\displaystyle k_{\max }}) مهم لتحسين الأداء.

أعمال موسعة

أُجريت العديد من الدراسات الموسّعة على خوارزمية البحث المكاني (SPO) نظرًا لبنيتها ومفهومها البسيطين؛ وقد ساهمت هذه الدراسات في تحسين أداء البحث الشامل لها واقتراح تطبيقات جديدة. [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]

مراجع

  1. ↑ تامورا، ك.؛ ياسودا، ك. (2011). "دراسة أولية للتحسين المستوحى من ديناميكيات الحلزون". مجلة IEEJ للمعاملات في الهندسة الكهربائية والإلكترونية . 6 (ملحق 1): 98-100 . doi : 10.1002/tee.20628 . S2CID 109093423 . 
  2. ↑ تامورا، ك.؛ ياسودا، ك. (2011). "التحسين المستوحى من الديناميكيات الحلزونية" . مجلة الذكاء الحسابي المتقدم والمعلوماتية الذكية . 132 (5): 1116-1121 . doi : 10.20965/jaciii.2011.p1116 .
  3. تامورا ، ك .؛ ياسودا، ك. (2016). "خوارزمية التحسين الحلزوني باستخدام اتجاهات الهبوط الدوري" . مجلة SICE للتحكم والقياس وتكامل الأنظمة . 6 (3): 133-143 . Bibcode : 2016JCMSI...9..134T . doi : 10.9746/jcmsi.9.134 .
  4. تامورا ، ك .؛ ياسودا، ك. (2020). "خوارزمية التحسين الحلزوني: شروط التقارب والإعدادات". معاملات IEEE في الأنظمة والإنسان وعلم التحكم الآلي: الأنظمة . 50 (1): 360-375 . doi : 10.1109/TSMC.2017.2695577 . S2CID 126109444 . 
  5. ↑ كروز-دوارته، خورخي م.؛ مارتن-دياز، إغناسيو؛ مونوز-مينخاريس، خو؛ سانشيز-غاليندو، لويس أ.؛ أفينا-سيرفانتس، خوان ج.؛ غارسيا-بيريز، أرتورو؛ كوريا-سيلي، س. رودريغو (2017). "دراسة أولية حول خوارزمية التحسين الحلزوني العشوائي" . المؤتمر الدولي الخريفي لعام 2017 لمعهد مهندسي الكهرباء والإلكترونيات حول الطاقة والإلكترونيات والحوسبة (ROPEC) . الصفحات 1-6 . doi : 10.1109/ROPEC.2017.8261609 . ISBN  978-1-5386-0819-7. S2CID 37580653 . 
  6. ↑ ناصر، أ.ن.ك.؛ توخي، م.و. (2015). "خوارزمية محسّنة للتحسين الديناميكي الحلزوني مع تطبيق هندسي". معاملات IEEE في الأنظمة والإنسان وعلم التحكم الآلي: الأنظمة . 45 (6): 943-954 . doi : 10.1109/tsmc.2014.2383995 . S2CID 24253496 . 
  7. ↑ ناصر، أ.ن.ك.؛ إسماعيل، ر.م.ت.ر.؛ توخي، م.أ. (2016). "خوارزمية ديناميكيات حلزونية تكيفية لتحسين عالمي مع تطبيق على نمذجة نظام مرن" (ملف PDF) . نمذجة الرياضيات التطبيقية . 40 ( 9-10 ): 5442-5461 . doi : 10.1016/j.apm.2016.01.002 .
  8. ↑ وادي، أ.؛ بنطرزي ، ح.؛ ريسوي، أ. (2013). "التصميم متعدد الأهداف للمرشحات الرقمية باستخدام تقنية التحسين الحلزوني" . SpringerPlus . 2 (461): 697-707 . doi : 10.1186/2193-1801-2-461 . PMC 3786071. PMID 24083108 .  
  9. ↑ بيناسلا، ل.؛ بلمداني، أ.؛ رحلي، م. (2014). "خوارزمية التحسين الحلزوني لحل مشكلة التوزيع الاقتصادي والانبعاثات المدمجة". المجلة الدولية لأنظمة الطاقة الكهربائية . 62 : 163-174 . Bibcode : 2014IJEPE..62..163B . doi : 10.1016/j.ijepes.2014.04.037 .
  10. ↑ سيدارتو، ك.أ.؛ كانيا، أ. (2015). "إيجاد جميع حلول أنظمة المعادلات غير الخطية باستخدام التحسين المستوحى من الديناميكيات الحلزونية مع التجميع" . مجلة الذكاء الحسابي المتقدم والمعلوماتية الذكية . 19 (5): 697-707 . doi : 10.20965/jaciii.2015.p0697 .
  11. ↑ كافيه، أ.؛ محجوبي، س. (أكتوبر 2019). "نهج تحسين الحلزون الهيبوتروكويدي لتحسين أبعاد وتصميم الهياكل الجمالونية ذات قيود التردد المتعددة". الهندسة باستخدام الحاسوب . 35 (4): 1443-1462 . doi : 10.1007/s00366-018-0675-6 . S2CID 54457145 .