التحسين الأمثل

التحسين الأمثل ( EO ) هو أسلوب استدلالي للتحسين مستوحى من نموذج باك-سنيبن للتنظيم الذاتي الحرج في مجال الفيزياء الإحصائية. صُمم هذا الأسلوب الاستدلالي في البداية لمعالجة مسائل التحسين التوافقي مثل مسألة البائع المتجول ومسألة الزجاج المغزلي ، على الرغم من أنه ثبتت فعاليته في مجالات التحسين.

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

يُعدّ العمل على التعقيد الحسابي، وتحديدًا إثبات وجود نقاط حرجة في مسائل NP-complete ، عنصرًا آخر في هذا اللغز ، حيث تتشتت الحلول شبه المثلى على نطاق واسع وتفصلها حواجز في فضاء البحث، مما يؤدي إلى تعثر خوارزميات البحث المحلي أو إعاقتها بشدة. وقد كان نموذج التنظيم الذاتي التطوري للحرجية الذي وضعه باك وسنيبن، وملاحظة النقاط الحرجة في مسائل التحسين التوافقي، هما ما أدى إلى تطوير التحسين الأمثل على يد ستيفان بوتشر وألون بيركوس.

صُممت خوارزمية EO كخوارزمية بحث محلية لمسائل التحسين التوافقي . على عكس الخوارزميات الجينية ، التي تعمل مع مجموعة من الحلول المرشحة، تُطوّر EO حلاً واحداً وتُجري تعديلات محلية على أسوأ مكوناته. يتطلب هذا اختيار تمثيل مناسب يسمح بتخصيص مقياس جودة ("اللياقة") لكل مكون من مكونات الحل. يختلف هذا عن المناهج الشاملة، مثل تحسين مستعمرات النمل والحوسبة التطورية ، التي تُخصص لياقة متساوية لجميع مكونات الحل بناءً على تقييمها الجماعي مقابل دالة الهدف. تُهيأ الخوارزمية بحل أولي، يمكن إنشاؤه عشوائياً أو اشتقاقه من عملية بحث أخرى.

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

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

تم تطبيق EO بشكل أساسي على المشكلات التوافقية مثل تقسيم الرسم البياني ومسألة البائع المتجول ، بالإضافة إلى المشكلات من الفيزياء الإحصائية مثل الزجاج المغزلي .

طُوِّرت خوارزمية التحسين المتطرف المعمم (GEO) للعمل على سلاسل البتات حيث تُحدَّد جودة المكونات بمعدل التغير المطلق للبت، أو بمساهمة البتات في جودة الحل الكلي. يشمل هذا العمل تطبيقات على مسائل تحسين الدوال القياسية، بالإضافة إلى مجالات المسائل الهندسية. ومن الامتدادات المشابهة لخوارزمية التحسين المتطرف خوارزمية التحسين المتطرف المستمر (CEO).

طُبقت خوارزمية تحسين الكائنات (EO) على تحويل الصور إلى صور نقطية، كما استُخدمت كبحث محلي بعد تطبيق خوارزمية تحسين مستعمرات النمل . واستُخدمت أيضًا لتحديد البنى في الشبكات المعقدة، ولحل مشكلة تتبع أهداف متعددة. وأخيرًا، أُجريت بعض الدراسات حول توزيع الاحتمالات المستخدم للتحكم في عملية الاختيار.

• الخوارزمية الجينية
• التلدين المحاكي

• باك، بير؛ تانغ، تشاو؛ ويزنفيلد، كورت (27 يوليو 1987). "التنظيم الذاتي الحرج: تفسير لضوضاء 1/f". رسائل المراجعة الفيزيائية . 59 (4). الجمعية الفيزيائية الأمريكية (APS): 381-384 . رمز Bibcode : 1987PhRvL..59..381B . doi : 10.1103/physrevlett.59.381 . ISSN 0031-9007 . PMID 10035754. S2CID 7674321 .   
• باك، بير؛ سنيبن، كيم (13 ديسمبر 1993). "التوازن المتقطع والحرجية في نموذج بسيط للتطور". رسائل المراجعة الفيزيائية . 71 (24). الجمعية الفيزيائية الأمريكية (APS): 4083-4086 . رمز Bibcode : 1993PhRvL..71.4083B . doi : 10.1103/physrevlett.71.4083 . ISSN 0031-9007 . PMID 10055149 .  
• بي تشيزمان، بي كانيفسكي، دبليو إم تايلور، "أين تكمن المشاكل الصعبة حقًا" ، وقائع المؤتمر الدولي الثاني عشر للذكاء الاصطناعي، (1991).
• جي إيسترات، " التعقيد الحسابي والتحولات الطورية "، وقائع المؤتمر السنوي الخامس عشر لمعهد مهندسي الكهرباء والإلكترونيات حول التعقيد الحسابي، 104-115 (2000)
• ستيفان بوتشر، ألون جي. بيركوس، "التحسين الأمثل: طرق مستمدة من التطور المشترك" ، وقائع مؤتمر الحوسبة الجينية والتطورية (1999).
• بوتشر، ستيفان (1999-01-01). "التحسين الأمثل لتقسيم الرسم البياني عند عتبة الترشيح". مجلة الفيزياء أ: الرياضية والعامة . 32 (28). دار نشر IOP: 5201-5211 . arXiv : cond-mat/9901353 . Bibcode : 1999JPhA...32.5201B . doi : 10.1088/0305-4470/32/28/302 . ISSN: 0305-4470 . S2CID : 7925735 .  
• بوتشر، ستيفان؛ بيركوس، ألون (2000)، "طريقة الطبيعة في التحسين"، الذكاء الاصطناعي ، 119 ( 1-2 ): 275-286 ، arXiv : cond-mat/9901351 ، doi : 10.1016/S0004-3702(00)00007-2 ، S2CID 7128022 
• بوتشر، س. (2000). "التحسين الأمثل: طرق استدلالية عبر الانهيارات التطورية المشتركة". الحوسبة في العلوم والهندسة . 2 (6). معهد مهندسي الكهرباء والإلكترونيات (IEEE): 75-82 . arXiv : cond-mat/0006374 . Bibcode : 2000CSE.....2f..75B . doi : 10.1109/5992.881710 . ISSN 1521-9615 . S2CID 7259036 .  
• بوتشر، ستيفان؛ بيركوس، ألون ج. (4 يونيو 2001). "التحسين باستخدام الديناميكيات القصوى". رسائل المراجعة الفيزيائية . 86 (23). الجمعية الفيزيائية الأمريكية (APS): 5211-5214 . arXiv : cond-mat/0010337 . Bibcode : 2001PhRvL..86.5211B . doi : 10.1103 /physrevlett.86.5211 . ISSN 0031-9007 . PMID 11384460. S2CID 3261749 .   
• دال، جيسبر؛ سيباني، باولو (2001). "محاكاة مونت كارلو أسرع عند درجات الحرارة المنخفضة: طريقة وقت الانتظار". مجلة اتصالات فيزياء الحاسوب . 141 (2): 260-267 . arXiv : cond-mat/0107475 . Bibcode : 2001CoPhC.141..260D . doi : 10.1016/s0010-4655(01)00412-x . ISSN: 0010-4655 . S2CID : 14585624 .  
• بوتشر، ستيفان؛ غريني، مايكل أنجلو (28 يناير 2002). "نموذج التشويش لخوارزمية التحسين الأمثل القصوى". مجلة الفيزياء أ: الرياضية والعامة . 35 (5). دار نشر IOP: 1109-1123 . arXiv : cond-mat/0110165 . Bibcode : 2002JPhA...35.1109B . doi : 10.1088/0305-4470/35/5/301 . ISSN: 0305-4470 . S2CID: 640976 .  
• سوهام مشول ومحمد باتوش، "التطابق القوي للنقاط لتسجيل الصور باستخدام التحسين مع الديناميكيات القصوى" ، ملاحظات المحاضرات في علوم الحاسوب 2449 ، 330-337 (2002).
• أونودي، روبرتو ن.؛ دي كاسترو، باولو أ. (2003). "التنظيم الذاتي الحرج، والتحسين، والتنوع البيولوجي". المجلة الدولية للفيزياء الحديثة ج . 14 (7). دار النشر العالمية العلمية المحدودة: 911-916 . arXiv : cond-mat/0302260 . Bibcode : 2003IJMPC..14..911O . doi : 10.1142/s0129183103005054 . ISSN: 0129-1831 . S2CID : 14553130 .  
• بوتشر، ستيفان؛ بيركوس، ألون ج. (24-06-2004). "التحسين الأمثل عند الانتقال الطوري لمسألة التلوين الثلاثي". مجلة Physical Review E. 69 ( 6) 066703. الجمعية الفيزيائية الأمريكية (APS). arXiv : cond-mat/0402282 . Bibcode : 2004PhRvE..69f6703B . doi : 10.1103/physreve.69.066703 . ISSN 1539-3755 . PMID 15244779. S2CID 3070942 .   
• ميدلتون، أ. آلان (14 مايو 2004). "تحسين التحسين الأمثل للزجاج الدوراني إيزينغ". مجلة Physical Review E ، المجلد 69 ، العدد 5، 055701. الجمعية الفيزيائية الأمريكية (APS): 055701(R). arXiv : cond-mat/0402295 . Bibcode : 2004PhRvE..69e5701M . doi : 10.1103/physreve.69.055701 . ISSN: 1539-3755 . PMID: 15244875. S2CID : 28439352 .   
• هايل مان، ف؛ هوفمان، ك. هـ؛ سالامون، ب (2004). "أفضل توزيع احتمالي ممكن على رتب التحسين القصوى". رسائل الفيزياء الأوروبية . 66 (3). دار نشر IOP: 305-310 . رمز Bibcode : 2004EL.....66..305H . doi : 10.1209/epl/i2004-10011-3 . ISSN 0295-5075 . S2CID 250810936 .  
• بونتوس سفينسون، "التحسين الأمثل للمعالجة المسبقة لتقارير المستشعرات"، وقائع SPIE 5429 ، 162-171 (2004)
• تشو، تاو؛ باي، وين-جي؛ تشنغ، لونغ-جيو؛ وانغ، بينغ-هونغ (2005-07-06). "التحسين الأمثل المستمر لمجموعات لينارد-جونز". مجلة Physical Review E. 72 ( 1) 016702. الجمعية الفيزيائية الأمريكية (APS). arXiv : cond-mat/0411428 . Bibcode : 2005PhRvE..72a6702Z . doi : 10.1103 / physreve.72.016702 . ISSN 1539-3755 . PMID 16090129. S2CID 26578844 .   
• دوتش، جوردي؛ أريناس، أليكس (24 أغسطس/آب 2005). "الكشف عن المجتمعات في الشبكات المعقدة باستخدام التحسين الأمثل". مجلة Physical Review E ، 72 (2)، 027104. الجمعية الفيزيائية الأمريكية (APS). arXiv : cond-mat/0501368 . Bibcode : 2005PhRvE..72b7104D . doi : 10.1103/physreve.72.027104 . ISSN: 1539-3755 . PMID: 16196754. S2CID : 13898113 .   
• أحمد، إي.؛ إليتربي، إم إف (2006). "حول التحسين التوافقي المستوحى من علم الأحياء". الرياضيات التطبيقية والحساب . 172 (1). إلسيفير بي في: 40-48 . doi : 10.1016/j.amc.2005.01.122 . ISSN 0096-3003 . 

• ستيفان بوتشر – قسم الفيزياء، جامعة إيموري
• ألون بيركوس – جامعة كليرمونت للدراسات العليا
• خوارزميات التحسين العالمي - النظرية والتطبيق - مؤرشفة بتاريخ 11 سبتمبر 2008 على موقع Wayback Machine - توماس وايز