Differential evolution
ارتقائی حساب میں، تفریق ارتقاء (DE) ایک ایسا طریقہ ہے جو معیار کی دی گئی پیمائش کے حوالے سے امیدوار کے حل کو بہتر بنانے کی بار بار کوشش کر کے کسی مسئلے کو بہتر بناتا ہے۔ اس طرح کے طریقوں کو عام طور پر میٹا ہیورسٹکس کے نام سے جانا جاتا ہے کیونکہ وہ بہتر مسئلے کے بارے میں بہت کم یا کوئی مفروضہ نہیں بناتے ہیں اور امیدوار کے حل کی بہت بڑی جگہیں تلاش کر سکتے ہیں۔ تاہم، ڈی ای جیسے میٹا تھیوریسٹکس اس بات کی ضمانت نہیں دیتے کہ کبھی بھی بہترین حل مل جائے گا۔ ڈی ای کو کثیر جہتی حقیقی قدر والے افعال کے لیے استعمال کیا جاتا ہے لیکن یہ بہتر بنائے جانے والے مسئلے کے میلان کو استعمال نہیں کرتا ہے، جس کا مطلب ہے کہ ڈی ای کو بہتر بنانے کے مسئلے کو تفریق کے قابل ہونے کی ضرورت نہیں ہے، جیسا کہ کلاسیکی اصلاح کے طریقوں جیسے گریڈینٹ ڈیسنٹ اور نیم نیوٹن طریقوں کے لیے ضروری ہے۔ لہذا DE کو اصلاح کے مسائل پر بھی استعمال کیا جا سکتا ہے جو مسلسل بھی نہیں ہیں، شور ہیں، وقت کے ساتھ تبدیل ہوتے ہیں، وغیرہ۔ ڈی ای امیدوار حل کی آبادی کو برقرار رکھتے ہوئے اور موجودہ حل کو اس کے سادہ فارمولوں کے مطابق جوڑ کر نئے امیدوار حل بنا کر، اور پھر جو بھی امیدوار حل ہاتھ میں موجود اصلاح کے مسئلے پر بہترین اسکور یا فٹنس رکھتا ہے اسے رکھ کر کسی مسئلے کو بہتر بناتا ہے۔ اس طرح، اصلاح کے مسئلے کو ایک بلیک باکس کے طور پر سمجھا جاتا ہے جو محض امیدوار کے حل کو دیکھتے ہوئے معیار کی پیمائش فراہم کرتا ہے اور اس لیے میلان کی ضرورت نہیں ہے۔ سٹورن اینڈ پرائس نے 1990 کی دہائی میں ڈی ای متعارف کرایا۔ متوازی کمپیوٹنگ، ملٹی آبجیکٹیو آپٹیمائزیشن، محدود اصلاح میں ڈی ای کے استعمال کے نظریاتی اور عملی پہلوؤں پر کتابیں شائع کی گئی ہیں، اور ان کتابوں میں اطلاق کے شعبوں کے سروے بھی شامل ہیں۔ ڈی ای کے کثیر جہتی تحقیقی پہلوؤں پر سروے جریدے کے مضامین میں مل سکتے ہیں۔ الگورتھم ڈی ای الگورتھم کا ایک بنیادی ورژن امیدوار حل (جسے ایجنٹ کہا جاتا ہے) کی آبادی کے ساتھ کام کرتا ہے۔ ان ایجنٹوں کو آبادی سے موجودہ ایجنٹوں کی پوزیشنوں کو یکجا کرنے کے لیے سادہ ریاضیاتی فارمولوں کا استعمال کرتے ہوئے سرچ اسپیس میں منتقل کیا جاتا ہے۔ اگر کسی ایجنٹ کی نئی پوزیشن میں بہتری ہے تو اسے قبول کر لیا جاتا ہے اور آبادی کا حصہ بن جاتا ہے، بصورت دیگر نئی پوزیشن کو آسانی سے مسترد کر دیا جاتا ہے۔ یہ عمل دہرایا جاتا ہے اور ایسا کرنے سے یہ امید کی جاتی ہے، لیکن اس کی ضمانت نہیں ہے کہ آخر کار ایک تسلی بخش حل دریافت ہو جائے گا۔ رسمی طور پر، فٹنس فنکشن ہونے دیں جسے کم سے کم کیا جانا چاہیے (نوٹ کریں کہ اس کے بجائے فنکشن پر غور کرکے زیادہ سے زیادہ کارکردگی کا مظاہرہ کیا جا سکتا ہے)۔ فنکشن ایک امیدوار حل کو حقیقی اعداد کے ویکٹر کی شکل میں دلیل کے طور پر لیتا ہے۔ یہ آؤٹ پٹ کے طور پر ایک حقیقی نمبر پیدا کرتا ہے جو دیئے گئے امیدوار حل کی فٹنس کی نشاندہی کرتا ہے۔ کا میلان معلوم نہیں ہے۔ مقصد ایک ایسا حل تلاش کرنا ہے جس کے لیے سرچ اسپیس میں سب کے لیے، جس کا مطلب ہے کہ یہ عالمی کم از کم ہے۔ آئیے آبادی میں ایک امیدوار حل (ایجنٹ) کو نامزد کریں۔ اس کے بعد بنیادی DE الگورتھم کو مندرجہ ذیل طور پر بیان کیا جا سکتا ہے: پیرامیٹرز کا انتخاب کریں، اور۔ آبادی کا سائز ہے، یعنی۔ امیدوار ایجنٹوں یا "والدین" کی تعداد ؛ ایک عام ترتیب 10 ہے۔ پیرامیٹر کو کراس اوور کا امکان کہا جاتا ہے اور پیرامیٹر کو تفریقی وزن کہا جاتا ہے۔ عام ترتیبات ہیں اور۔ ان انتخاب سے اصلاح کی کارکردگی بہت زیادہ متاثر ہو سکتی ہے ؛ نیچے دیکھیں۔ سرچ اسپیس میں بے ترتیب پوزیشن والے تمام ایجنٹوں کو شروع کریں۔ جب تک کہ اختتامی معیار پورا نہ ہو جائے (مثال کے طور پر۔ انجام دی گئی تکرار کی تعداد، یا مناسب فٹنس تک پہنچ گئی)، درج ذیل کو دہرائیں: آبادی میں ہر ایجنٹ کے لیے: تین ایجنٹوں کا انتخاب کریں، اور بے ترتیب طور پر آبادی سے، وہ ایک دوسرے کے ساتھ ساتھ ایجنٹ سے بھی الگ ہونے چاہئیں۔ (اسے "بیس" ویکٹر کہا جاتا ہے۔) ایک بے ترتیب اشاریہ کا انتخاب کریں جہاں مسئلے کی جہت کو بہتر بنایا جا رہا ہو۔ ایجنٹ کی ممکنہ طور پر نئی پوزیشن کا حساب اس طرح کریں: ہر ایک کے لیے یکساں طور پر تقسیم شدہ بے ترتیب نمبر منتخب کریں اگر یا پھر دوسری صورت میں سیٹ کریں۔ (اشاریہ کی پوزیشن کو یقینی طور پر تبدیل کیا جاتا ہے۔) اگر پھر آبادی میں ایجنٹ کو بہتر یا مساوی امیدوار حل سے تبدیل کریں۔ اس آبادی میں سے ایجنٹ کا انتخاب کریں جس میں بہترین فٹنس ہو اور اسے بہترین امیدوار حل کے طور پر واپس کریں۔ پیرامیٹر کا انتخاب ڈی ای پیرامیٹرز کا انتخاب، اور اصلاح کی کارکردگی پر بڑا اثر ڈال سکتا ہے۔ اس لیے اچھی کارکردگی دینے والے ڈی ای پیرامیٹرز کا انتخاب بہت تحقیق کا موضوع رہا ہے۔ پیرامیٹر کے انتخاب کے لیے انگوٹھے کے اصول اسٹورن اور دیگر نے وضع کیے تھے۔ اور لیو اور لیمپینن۔ پیرامیٹر کے انتخاب کے حوالے سے ریاضیاتی کنورجنس تجزیہ زہری نے کیا تھا۔ اصلاح کی کارکردگی کو بہتر بنانے کی کوشش میں ڈی ای الگورتھم کے متغیرات مسلسل تیار کیے جا رہے ہیں۔ اوپر دیے گئے بنیادی الگورتھم میں کراس اوور انجام دینے اور ایجنٹوں کی تغیر کے لیے بہت سی مختلف اسکیمیں ممکن ہیں، مثال کے طور پر دیکھیں۔ مصنوعی مکھی کالونی الگورتھم CMA-ES ارتقاء کی حکمت عملی جینیاتی الگورتھم حوالہ جات ارتقاء الگورتھم بھی دیکھیں۔