Estimation of distribution algorithm
ڈسٹری بیوشن الگورتھم کا تخمینہ (ای ڈی اے)، جسے بعض اوقات پروبیبلسٹک ماڈل بلڈنگ جینیٹک الگورتھم (پی ایم بی جی اے) کہا جاتا ہے، اسٹاکاسٹک آپٹیمائزیشن کے طریقے ہیں جو امید افزا امیدوار حل کے واضح پروبیبلسٹک ماڈل بنا کر اور نمونے لے کر زیادہ سے زیادہ تلاش کی رہنمائی کرتے ہیں۔ آپٹیمائزیشن کو ممکنہ ماڈل کی اضافی اپ ڈیٹس کے ایک سلسلے کے طور پر دیکھا جاتا ہے، جس کا آغاز ماڈل سے ہوتا ہے جو قابل قبول حل سے پہلے ایک غیر معلوماتی کوڈنگ کرتا ہے اور اس ماڈل کے ساتھ ختم ہوتا ہے جو صرف عالمی آپٹیما پیدا کرتا ہے۔ ای ڈی اے کا تعلق ارتقائی الگورتھم کی کلاس سے ہے۔ ای ڈی اے اور زیادہ تر روایتی ارتقائی الگورتھم کے درمیان بنیادی فرق یہ ہے کہ ارتقائی الگورتھم ایک یا زیادہ تغیر آپریٹرز کے ذریعہ بیان کردہ ایک مضمر تقسیم کا استعمال کرتے ہوئے نئے امیدوار حل تیار کرتے ہیں، جبکہ ای ڈی اے ایک واضح امکان کی تقسیم کا استعمال کرتے ہیں جو بیسیئن نیٹ ورک، ایک ملٹی ویریٹ نارمل ڈسٹری بیوشن، یا کسی اور ماڈل کلاس کے ذریعے انکوڈ کیا جاتا ہے۔ اسی طرح دیگر ارتقائی الگورتھم کی طرح، ای ڈی اے کو ویکٹر سے لے کر ایل آئی ایس پی سٹائل ایس کے تاثرات تک متعدد نمائندگی پر بیان کردہ اصلاح کے مسائل کو حل کرنے کے لیے استعمال کیا جا سکتا ہے، اور امیدوار کے حل کے معیار کا اکثر ایک یا زیادہ معروضی افعال کا استعمال کرتے ہوئے جائزہ لیا جاتا ہے۔ ای ڈی اے کے عمومی طریقہ کار کو درج ذیل میں بیان کیا گیا ہے: t: = 0 ماڈل M (0) کو قابل قبول حل پر یکساں تقسیم کی نمائندگی کرنے کے لیے شروع کریں جبکہ (اختتامی معیار کو پورا نہیں کیا گیا) P: = نمونہ لے کر N> 0 امیدوار حل پیدا کریں M (t) F: = P M (t + 1) میں تمام امیدوار حل کا اندازہ کریں: = adjust _ models (P, F, M (t) t: = t + 1 اصلاح میں واضح ممکنہ ماڈل کا استعمال EDAs کو ممکنہ طور پر اصلاح کے مسائل کو حل کرنے کی اجازت دیتا ہے جو زیادہ تر روایتی ارتقائی الگورتھم اور روایتی اصلاح کی تکنیکوں کے لیے بدنام مشکل تھے، جیسے کہ اعلی سطح کے ایپیسٹاسس والے مسائل۔ بہر حال، ای ڈی اے کا فائدہ یہ بھی ہے کہ یہ الگورتھم ایک اصلاح پسند پریکٹیشنر کو ممکنہ ماڈلز کی ایک سیریز فراہم کرتے ہیں جو حل کیے جانے والے مسئلے کے بارے میں بہت سی معلومات ظاہر کرتے ہیں۔ اس معلومات کو بدلے میں مقامی تلاش کے لیے مسئلہ مخصوص پڑوس کے آپریٹرز کو ڈیزائن کرنے، اسی طرح کے مسئلے پر ای ڈی اے کے مستقبل کے رنوں کو تعصب کرنے، یا مسئلے کا ایک موثر کمپیوٹیشنل ماڈل بنانے کے لیے استعمال کیا جا سکتا ہے۔ مثال کے طور پر، اگر آبادی کی نمائندگی لمبائی 4 کے بٹ تاروں سے کی جاتی ہے، تو ای ڈی اے چار امکانات (پی 1، پی 2، پی 3، پی 4) کے واحد ویکٹر کا استعمال کرتے ہوئے امید افزا حل کی آبادی کی نمائندگی کر سکتا ہے جہاں پی کا ہر جزو اس پوزیشن کے 1 ہونے کے امکان کی وضاحت کرتا ہے۔ اس امکانی ویکٹر کا استعمال کرتے ہوئے امیدوار حل کی صوابدیدی تعداد بنانا ممکن ہے۔ تقسیم الگورتھم کا تخمینہ (ای ڈی اے) یہ سیکشن پیچیدگی کی مختلف سطحوں کے کچھ معروف ای ڈی اے کے ذریعہ بنائے گئے ماڈلز کی وضاحت کرتا ہے۔ اسے ہمیشہ نسل کی آبادی، سلیکشن آپریٹر، ماڈل بنانے والا آپریٹر اور سیمپلنگ آپریٹر سمجھا جاتا ہے۔ غیر متغیر فیکٹرائزیشن سب سے آسان ای ڈی اے یہ فرض کرتے ہیں کہ فیصلہ متغیر آزاد ہیں، یعنی۔ ۔ لہذا، غیر متغیر ای ڈی اے صرف غیر متغیر اعداد و شمار پر انحصار کرتے ہیں اور کثیر متغیر تقسیم کو غیر متغیر امکانات کی تقسیم کے پروڈکٹ کے طور پر فیکٹرائز کیا جانا چاہیے، اس طرح کے فیکٹرائزیشن بہت سے مختلف ای ڈی اے میں استعمال ہوتے ہیں، اس کے بعد ہم ان میں سے کچھ کی وضاحت کرتے ہیں۔ غیر متغیر مارجنل ڈسٹری بیوشن الگورتھم (یو ایم ڈی اے) یو ایم ڈی اے ایک سادہ ای ڈی اے ہے جو ایک آپریٹر کا استعمال کرتے ہوئے ایک منتخب آبادی سے مارجنل امکانات کا اندازہ لگاتا ہے۔ یہ فرض کر کے کہ عناصر پر مشتمل ہے، امکانات پیدا کرتا ہے: یو ایم ڈی اے کے ہر قدم کو آبادی پر مبنی انکریمنٹل لرننگ (پی بی آئی ایل) کے طور پر بیان کیا جا سکتا ہے۔ پی بی آئی ایل، آبادی کی نمائندگی اپنے ماڈل کے ذریعے کرتا ہے، جس سے وہ نئے حل کا نمونہ لیتا ہے اور ماڈل کو اپ ڈیٹ کرتا ہے۔ ہر نسل میں، افراد کا نمونہ لیا جاتا ہے اور ان کا انتخاب کیا جاتا ہے۔ اس کے بعد ایسے افراد کو ماڈل کو مندرجہ ذیل طور پر اپ ڈیٹ کرنے کے لیے استعمال کیا جاتا ہے جہاں سیکھنے کی شرح کی وضاحت کرنے والا ایک پیرامیٹر ہوتا ہے، ایک چھوٹی سی قیمت اس بات کا تعین کرتی ہے کہ پچھلے ماڈل کو نمونے کے نئے حل کے ذریعے صرف قدرے تبدیل کیا جانا چاہیے۔ پی بی آئی ایل کو کمپیکٹ جینیٹک الگورتھم (سی جی اے) کے طور پر بیان کیا جا سکتا ہے۔ سی جی اے، غیر متغیر تقسیم کے ذریعے بیان کردہ مضمر آبادیوں پر بھی انحصار کرتا ہے۔ ہر نسل میں، دو افراد کے نمونے لیے جاتے ہیں۔ اس کے بعد آبادی کو فٹنس کی گھٹتی ہوئی ترتیب میں ترتیب دیا جاتا ہے، جس میں بہترین اور بدترین حل ہوتا ہے۔ سی جی اے غیر متغیر امکانات کا تخمینہ اس طرح لگاتا ہے جہاں، سیکھنے کی شرح کی مستقل وضاحت ہوتی ہے، جسے عام طور پر مقرر کیا جاتا ہے۔ سی جی اے کو بائی ویریٹ فیکٹرائزیشن کے طور پر بیان کیا جا سکتا ہے حالانکہ یونی ویریٹ ماڈلز کو مؤثر طریقے سے شمار کیا جا سکتا ہے، بہت سے معاملات میں وہ جی اے سے بہتر کارکردگی فراہم کرنے کے لیے کافی نمائندہ نہیں ہوتے ہیں۔ اس طرح کی خرابی پر قابو پانے کے لیے، ای ڈی اے کمیونٹی میں بائی ویریٹ فیکٹرائزیشنز کا استعمال تجویز کیا گیا تھا، جس میں متغیرات کے جوڑوں کے درمیان انحصار کا نمونہ بنایا جا سکتا ہے۔ ایک دو متغیر فیکٹرائزیشن کو مندرجہ ذیل طور پر بیان کیا جا سکتا ہے، جہاں اس پر منحصر ممکنہ متغیر ہوتا ہے، یعنی۔ ۔ دو متغیر اور کثیر متغیر تقسیم کو عام طور پر ممکنہ گرافیکل ماڈل (گراف) کے طور پر پیش کیا جاتا ہے، جس میں کنارے شماریاتی انحصار (یا مشروط امکانات) کی نشاندہی کرتے ہیں اور عمودی متغیرات کی نشاندہی کرتے ہیں۔ ڈیٹا لنکج لرننگ سے پی جی ایم کے ڈھانچے کو سیکھنے کے لیے استعمال کیا جاتا ہے۔ باہمی معلومات کو زیادہ سے زیادہ ان پٹ کلسٹرنگ (ایم آئی ایم آئی سی) ایم آئی ایم آئی سی متغیرات کے درمیان مسلسل انحصار کی نمائندگی کرنے والے سلسلہ نما ماڈل میں مشترکہ امکان کی تقسیم کو فیکٹرائز کرتا ہے۔ یہ فیصلہ متغیرات کی ترتیب کو تلاش کرتا ہے، اس طرح کہ حقیقی امکان کی تقسیم کے سلسلے میں کل بیک-لیبلر انحراف کو کم سے کم کرتا ہے، یعنی۔ ۔ ایم آئی ایم آئی سی ماڈل ایک تقسیم نئے حلوں کا نمونہ بائیں سے دائیں متغیر تک لیا جاتا ہے، پہلا آزادانہ طور پر تیار کیا جاتا ہے اور دیگر مشروط امکانات کے مطابق۔ چونکہ تخمینہ شدہ تقسیم کو ہر نسل میں دوبارہ شمار کیا جانا چاہیے، اس لیے ایم آئی ایم آئی سی مندرجہ ذیل طریقے سے ٹھوس آبادی کا استعمال کرتا ہے۔ سب سے پہلے، تصادفی طور پر منتخب کردہ متغیر کو گراف میں نوڈ کے طور پر شامل کیا جاتا ہے، گراف میں موجود متغیرات میں سے کسی ایک پر سب سے زیادہ منحصر متغیر کو ان میں سے منتخب کیا جاتا ہے جو ابھی گراف میں نہیں ہیں، اس طریقہ کار کو اس وقت تک دہرایا جاتا ہے جب تک کہ کوئی باقی متغیر گراف میں موجود کسی متغیر پر منحصر نہ ہو (حد قیمت کے مطابق تصدیق شدہ)۔ نتیجے میں ماڈل ایک جنگل ہے جس میں متعدد درختوں کی جڑیں نوڈس پر ہیں۔ غیر جڑ متغیرات پر غور کرتے ہوئے، بی ایم ڈی اے ایک فیکٹرائزڈ تقسیم کا تخمینہ لگاتا ہے جس میں جڑ متغیرات کو آزادانہ طور پر نمونے لیا جا سکتا ہے، جبکہ دیگر تمام کو پیرنٹ متغیر کے مطابق ہونا چاہیے۔ بی ایم ڈی اے کے ہر مرحلے کی تعریف مندرجہ ذیل ملٹی ویریٹ فیکٹرائزیشن کے طور پر کی گئی ہے۔ ای ڈی اے کی ترقی کا اگلا مرحلہ ملٹی ویریٹ فیکٹرائزیشن کا استعمال تھا۔ اس صورت میں، مشترکہ امکان کی تقسیم کو عام طور پر محدود سائز کے متعدد اجزاء میں فیکٹرائز کیا جاتا ہے۔ پی جی ایم کی انکوڈنگ ملٹی ویریٹ ڈسٹری بیوشن سیکھنا ایک کمپیوٹیشنل طور پر مہنگا کام ہے، اس لیے ای ڈی اے کے لیے یہ معمول ہے کہ وہ دو متغیر اعدادوشمار سے ملٹی ویریٹ اعدادوشمار کا اندازہ لگائیں۔ اس طرح کی نرمی پی جی ایم کو کثیر الجہتی وقت میں تعمیر کرنے کی اجازت دیتی ہے ؛ تاہم، یہ اس طرح کے ای ڈی اے کی عامیت کو بھی محدود کرتی ہے۔ توسیعی کمپیکٹ جینیاتی الگورتھم (ای سی جی اے) ای سی جی اے پہلے ای ڈی اے میں سے ایک تھا جس نے ملٹی ویریٹ فیکٹرائزیشنز کو استعمال کیا، جس میں فیصلہ متغیرات کے درمیان اعلی درجے کے انحصار کو ماڈل کیا جا سکتا ہے۔ اس کا نقطہ نظر ملٹی ویریٹ مارجنل ڈسٹری بیوشن کے پروڈکٹ میں مشترکہ امکان کی تقسیم کو فیکٹرائز کرتا ہے۔ فرض کریں کہ ذیلی سیٹوں کا ایک مجموعہ ہے، جس میں ہر ایک لنکج سیٹ ہے، جس میں متغیرات ہوتے ہیں۔ فیکٹرائزڈ جوائنٹ پروبیبلٹی ڈسٹری بیوشن کی نمائندگی مندرجہ ذیل طریقے سے کی جاتی ہے۔ ای سی جی اے نے "لنکیج لرننگ" کی اصطلاح کو ایسے طریقہ کار کے طور پر مقبول کیا جو لنکیج سیٹوں کی شناخت کرتے ہیں۔ اس کا ربط سیکھنے کا طریقہ کار دو اقدامات پر منحصر ہے: (1) ماڈل پیچیدگی (ایم سی) اور (2) کمپریسڈ پاپولیشن پیچیدگی (سی پی سی)۔ ایم سی تمام معمولی امکانات کو ذخیرہ کرنے کے لیے درکار بٹس کی تعداد کے لحاظ سے ماڈل کی نمائندگی کے سائز کی مقدار طے کرتا ہے۔ دوسری طرف سی پی سی، تمام پارٹیشنوں پر مارجنل ڈسٹری بیوشن کی اینٹروپی کے لحاظ سے ڈیٹا کمپریشن کی مقدار طے کرتا ہے، جہاں منتخب آبادی کا سائز ہے، لنکج سیٹ میں فیصلہ متغیرات کی تعداد ہے اور یہ متغیرات کی مشترکہ اینٹروپی ہے۔ ای سی جی اے میں لنکج لرننگ مندرجہ ذیل کام کرتی ہے: (1) ہر متغیر کو کلسٹر میں داخل کریں، (2) موجودہ لنکج سیٹ کے سی سی سی = ایم سی + سی پی سی کا حساب لگائیں، (3) کلسٹرز کے جوڑوں کو جوڑ کر فراہم کردہ سی سی سی پر اضافے کی تصدیق کریں، (4) مؤثر طریقے سے ان کلسٹرز میں شامل ہو جائیں جن میں سب سے زیادہ سی سی سی بہتری ہو۔ یہ طریقہ کار اس وقت تک دہرایا جاتا ہے جب تک کہ سی سی سی میں کوئی بہتری ممکن نہ ہو اور لنکج ماڈل تیار نہ ہو جائے۔ ای سی جی اے ٹھوس آبادیوں کے ساتھ کام کرتا ہے، لہذا، ای سی جی اے کے ذریعہ تیار کردہ فیکٹرائزڈ ڈسٹری بیوشن ماڈل کا استعمال کرتے ہوئے، اسے بیسیئن آپٹیمائزیشن الگورتھم (بی او اے) کے طور پر بیان کیا جاسکتا ہے۔ بی او اے امید افزا حل کے ماڈل اور نمونے لینے کے لیے بیسیئن نیٹ ورک کا استعمال کرتا ہے۔ بایسیئن نیٹ ورک ایسائکلک گراف کی ہدایت کرتے ہیں، جن میں متغیرات کی نمائندگی کرنے والے نوڈس اور متغیرات کے جوڑے کے درمیان مشروط امکانات کی نمائندگی کرنے والے کنارے ہوتے ہیں۔ متغیر کی قدر کو زیادہ سے زیادہ دیگر متغیرات پر مشروط کیا جا سکتا ہے، جس میں اس کی وضاحت کی گئی ہے۔ بی او اے ایک پی جی ایم انکوڈنگ بناتا ہے جو ایک فیکٹرائزڈ مشترکہ تقسیم ہے، جس میں نیٹ ورک کے پیرامیٹرز، یعنی۔ مشروط امکانات کا تخمینہ منتخب آبادی سے زیادہ سے زیادہ امکانات کا تخمینہ لگانے والے کا استعمال کرتے ہوئے لگایا جاتا ہے۔ دوسری طرف بایسیئن نیٹ ورک کا ڈھانچہ بار بار بنایا جانا چاہیے (لنکج-لرننگ)۔ یہ کناروں کے بغیر نیٹ ورک سے شروع ہوتا ہے اور، ہر قدم پر، کنارے کا اضافہ کرتا ہے جو کچھ اسکورنگ میٹرک کو بہتر بناتا ہے (مثال کے طور پر۔ امکانات کے مساوی (بی ڈی ای) کے ساتھ بایسیئن معلومات کا معیار (بی آئی سی) یا بایسیئن-ڈیرچلیٹ میٹرک۔ اسکورنگ میٹرک منتخب شدہ آبادی کے ماڈلنگ میں اس کی درستگی کے مطابق نیٹ ورک کے ڈھانچے کا جائزہ لیتا ہے۔ بلٹ نیٹ ورک سے، بی او اے نمونے نئے امید افزا حل مندرجہ ذیل ہیں: (1) یہ ہر متغیر کے لیے آبائی ترتیب کا حساب لگاتا ہے، ہر نوڈ اس کے والدین سے پہلے ہوتا ہے ؛ (2) ہر متغیر کو اس کے والدین کے لیے مشروط طور پر نمونہ لیا جاتا ہے۔ اس طرح کے منظر نامے کو دیکھتے ہوئے، ہر بی او اے مرحلے کو لنکج-ٹری جینیٹک الگورتھم (ایل ٹی جی اے) کے طور پر بیان کیا جا سکتا ہے۔ ایل ٹی جی اے زیادہ تر ای ڈی اے سے اس لحاظ سے مختلف ہے کہ یہ واضح طور پر امکان کی تقسیم کا نمونہ نہیں ہے بلکہ صرف ایک لنکج ماڈل ہے، جسے لنکج-ٹری کہا جاتا ہے۔ لنکیج لنکیج سیٹوں کا ایک مجموعہ ہے جس سے کوئی امکانی تقسیم وابستہ نہیں ہے، لہذا، براہ راست نئے حل کا نمونہ لینے کا کوئی طریقہ نہیں ہے۔ لنکیج ماڈل ایک لنکیج ٹری ہے جو فیملی آف سیٹس (ایف او ایس) کے طور پر ذخیرہ کیا جاتا ہے۔ لنکیج-ٹری سیکھنے کا طریقہ کار ایک درجہ بندی کلسٹرنگ الگورتھم ہے، جو مندرجہ ذیل کام کرتا ہے۔ ہر مرحلے پر دو قریب ترین کلسٹرز اور ضم ہو جاتے ہیں، یہ طریقہ کار اس وقت تک دہرایا جاتا ہے جب تک کہ صرف ایک کلسٹر باقی نہ رہ جائے، ہر ذیلی درخت کو ذیلی سیٹ کے طور پر محفوظ کیا جاتا ہے۔ ایل ٹی جی اے ایک "بہترین اختلاط" کے طریقہ کار کی رہنمائی کے لیے استعمال ہوتا ہے جو ریکومبینیشن آپریٹر سے ملتا جلتا ہے لیکن صرف بہتر چالوں کو قبول کرتا ہے۔ ہم اسے اس طرح ظاہر کرتے ہیں، جہاں اشارے سے اشارہ شدہ جینیاتی مواد کی منتقلی کی نشاندہی ہوتی ہے۔ ان پٹ: ذیلی مجموعوں اور آبادی کا ایک خاندان آؤٹ پٹ: ایک آبادی۔ ہر ایک کے لیے ہر ایک کے لیے بے ترتیب: =: = کا انتخاب کریں اگر پھر واپسی ہو تو ایل ٹی جی اے عام سلیکشن آپریٹرز کو لاگو نہیں کرتا، اس کے بجائے، انتخاب دوبارہ ملاپ کے دوران کیا جاتا ہے۔ اسی طرح کے خیالات کو عام طور پر مقامی سرچ ہیورسٹکس میں لاگو کیا گیا ہے اور اس لحاظ سے ایل ٹی جی اے کو ایک ہائبرڈ طریقہ کے طور پر دیکھا جا سکتا ہے۔ خلاصہ یہ ہے کہ ایل ٹی جی اے کے ایک مرحلے کی تعریف دیگر امکانی مجموعوں (پی سی) سیکھنے کے ساتھ پہاڑی چڑھائی (ایچ سی ڈبلیو ایل) ملٹی ویریٹ نارمل الگورتھم (ای ایم این اے) کا تخمینہ بیسیئن نیٹ ورک الگورتھم کا تخمینہ (ای بی این اے) معمول کی تقسیم کے ویکٹروں کے ذریعے سیکھنے کے ساتھ اسٹاکاسٹک پہاڑی چڑھائی (ایس ایچ سی ایل وی این ڈی) حقیقی کوڈڈ پی بی آئی ایل سیلفش جین الگورتھم (ایس جی) کمپیکٹ پارٹیکل ڈفریینشل ایوولوشن (سی ڈی ای) اور اس کے متغیرات کمپیکٹ پارٹیکل سوارم آپٹیمائزیشن (سی پی ایس او) کمپیکٹ بیکٹیریل فورجنگ آپٹیمائزیشن (سی بی ایف او) امکانی اضافی پروگرام ارتقاء (پی آئی پی ای) گوسیئن کا تخمینہ کے طور پر کی گئی ہے۔