Population model (evolutionary algorithm)
ارتقائی الگورتھم (ای اے) کا آبادی ماڈل اس کی آبادی کی ساختی خصوصیات کو بیان کرتا ہے جس کے تابع اس کے اراکین ہوتے ہیں۔ آبادی ای اے کے تمام مجوزہ حل کا مجموعہ ہے جس پر ایک تکرار میں غور کیا جاتا ہے، جسے حیاتیاتی رول ماڈل کے مطابق افراد بھی کہا جاتا ہے۔ آبادی کے افراد طریقہ کار کے جینیاتی آپریٹرز کی مدد سے مزید افراد کو اولاد کے طور پر پیدا کر سکتے ہیں۔ ای اے میں آبادی کا سب سے آسان اور وسیع پیمانے پر استعمال ہونے والا ماڈل عالمی یا پینمیکٹک ماڈل ہے، جو غیر ساختہ آبادی سے مطابقت رکھتا ہے۔ یہ ہر فرد کو اجازت دیتا ہے کہ وہ آبادی کے کسی بھی دوسرے فرد کو کراس اوور کے ذریعے اولاد کی پیداوار کے لیے شراکت دار کے طور پر منتخب کر سکے، جس کے تحت انتخاب کی تفصیلات غیر متعلقہ ہیں جب تک کہ افراد کی فٹنس اہم کردار ادا کرتی ہے۔ عالمی ساتھی کے انتخاب کی وجہ سے، چند نسلوں کے بعد آبادی میں قدرے بہتر افراد کی جینیاتی معلومات غالب ہو سکتی ہیں (ای اے کی تکرار)، بشرطیکہ اس مرحلے میں کوئی بہتر دوسری اولاد سامنے نہ آئی ہو۔ اگر اس طرح پایا جانے والا حل زیادہ سے زیادہ مطلوب نہیں ہے، تو اسے قبل از وقت کنورجنس کہا جاتا ہے۔ یہ اثر پینمیکٹک آبادیوں میں زیادہ کثرت سے دیکھا جا سکتا ہے۔ فطرت میں عالمی ملاپ کے تالاب شاذ و نادر ہی پائے جاتے ہیں۔ جو چیز غالب ہے وہ مقامی فاصلے کی وجہ سے ایک مخصوص اور محدود تنہائی ہے۔ نتیجے میں مقامی محلے ابتدائی طور پر آزادانہ طور پر تیار ہوتے ہیں اور متغیرات کے کئی نسلوں تک برقرار رہنے کا زیادہ امکان ہوتا ہے۔ نتیجے کے طور پر، جین پول میں جینو ٹائپک تنوع پینمیکٹک آبادی کے مقابلے میں زیادہ دیر تک محفوظ رہتا ہے۔ اس لیے پہلے کی عالمی آبادی کو ذیلی ڈھانچوں کے ذریعے تقسیم کرنا واضح ہے۔ اس مقصد کے لیے دو بنیادی ماڈل متعارف کرائے گئے، جزیرے کے ماڈل، جو آبادی کی مقررہ ذیلی آبادی میں تقسیم پر مبنی ہیں جو وقتا فوقتا افراد کا تبادلہ کرتے ہیں، اور پڑوس کے ماڈل، جو افراد کو اوور لیپنگ محلوں میں تفویض کرتے ہیں، جسے سیلولر جینیاتی یا ارتقائی الگورتھم (سی جی اے یا سی ای اے) بھی کہا جاتا ہے۔ آبادی کی متعلقہ تقسیم بھی طریقہ کار کے متعلقہ متوازی ہونے کا مشورہ دیتی ہے۔ اس وجہ سے، ای اے کے متوازی ہونے کے سلسلے میں ادب میں آبادی کے نمونوں کے موضوع پر بھی کثرت سے بحث کی جاتی ہے۔ جزیرے کے نمونے جزیرے کے نمونے میں، جسے ہجرت کا نمونہ یا موٹے دانے والا نمونہ بھی کہا جاتا ہے، ارتقاء سختی سے منقسم ذیلی آبادیوں میں ہوتا ہے۔ ان کو پینمیکٹک طور پر منظم کیا جا سکتا ہے، لیکن ہونا ضروری نہیں ہے۔ وقتا فوقتا افراد کا تبادلہ ہوتا ہے، جسے ہجرت کہا جاتا ہے۔ تبادلے کے درمیان کے وقت کو ایک دور کہا جاتا ہے اور اس کے اختتام کو مختلف معیارات سے متحرک کیا جا سکتا ہے: جیسے۔ ایک مقررہ وقت کے بعد یا مکمل نسلوں کی دی گئی تعداد کے بعد، یا جمود کے واقع ہونے کے بعد۔ جمود کا پتہ لگایا جا سکتا ہے، مثال کے طور پر، اس حقیقت سے کہ جزیرے میں کئی نسلوں سے فٹنس میں کوئی بہتری نہیں آئی ہے۔ جزیرے کے ماڈل مختلف قسم کی حکمت عملی کے پیرامیٹرز متعارف کراتے ہیں: ذیلی آبادی کی تعداد ذیلی آبادی کا سائز جزائر کے درمیان پڑوس کے تعلقات: وہ اس بات کا تعین کرتے ہیں کہ کون سے جزائر پڑوسی سمجھے جاتے ہیں اور اس طرح افراد کا تبادلہ کر سکتے ہیں، ایک سادہ یک طرفہ انگوٹھی (سیاہ تیر) کی تصویر دیکھیں اور اضافی دو طرفہ پڑوس کے تعلقات (اضافی سبز تیر) کے ذریعے اس کی توسیع کسی دور کے خاتمے کے لیے معیار، ہم وقت یا غیر ہم وقت ہجرت کی شرح: ہجرت میں شامل افراد کی تعداد یا تناسب۔ مہاجر انتخاب: اس کے بہت سے متبادل ہیں۔ ای۔ جی۔ بہترین افراد بدترین یا بے ترتیب طور پر منتخب کردہ افراد کی جگہ لے سکتے ہیں۔ ہجرت کی شرح پر منحصر ہے، یہ ایک وقت میں ایک یا زیادہ افراد کو متاثر کر سکتا ہے۔ ان پیرامیٹرز کے ساتھ، انتخاب کے دباؤ کو کافی حد تک متاثر کیا جا سکتا ہے۔ مثال کے طور پر، یہ جزائر کے باہم مربوط ہونے کے ساتھ بڑھتا ہے اور ذیلی آبادی کی تعداد یا دور کی لمبائی کے ساتھ کم ہوتا ہے۔ پڑوس کے ماڈل یا سیلولر ارتقائی الگورتھم پڑوس کے ماڈل، جسے بازی کا ماڈل یا باریک دانے والا ماڈل بھی کہا جاتا ہے، آبادی کے افراد کے درمیان ایک ٹپوولوجیکل پڑوس کے تعلقات کی وضاحت کرتا ہے جو ان کی فینوٹائپک خصوصیات سے آزاد ہے۔ اس ماڈل کا بنیادی خیال ای اے آبادی کو ایک خاص ڈھانچہ فراہم کرنا ہے جس کی وضاحت منسلک گراف کے طور پر کی گئی ہے، جس میں ہر ورٹیکس ایک فرد ہے جو اپنے قریبی پڑوسیوں کے ساتھ بات چیت کرتا ہے۔ خاص طور پر، افراد کو تصوراتی طور پر ٹورائڈل میش میں سیٹ کیا جاتا ہے، اور انہیں صرف قریبی افراد کے ساتھ دوبارہ جوڑنے کی اجازت ہوتی ہے۔ یہ ایک قسم کے محلے کی طرف لے جاتا ہے جسے فاصلے کے لحاظ سے تنہائی کہا جاتا ہے۔ کسی فرد کے ممکنہ ساتھیوں کے مجموعے کو اس کا پڑوس یا ڈیم کہا جاتا ہے۔ ملحقہ شکل اس بات کی وضاحت کرتی ہے کہ پیلے رنگ کے نشان والے دو افراد کے دو قدرے اوور لیپنگ محلوں کو دکھا کر، جس کے ذریعے جینیاتی معلومات دونوں ڈیموں کے درمیان پھیل سکتی ہیں۔ یہ معلوم ہے کہ اس قسم کے الگورتھم میں، اسی طرح کے افراد کلسٹر ہوتے ہیں اور ایسی طاقتیں بناتے ہیں جو ڈیم حدود سے آزاد ہوتی ہیں اور خاص طور پر، ڈیم سے بڑی ہو سکتی ہیں۔ ملحقہ گروہوں کے درمیان کوئی واضح حد نہیں ہے، اور قریبی مقامات کو مسابقتی افراد آسانی سے آباد کر سکتے ہیں اور شاید اس عمل کے دوران حل کے مندرجات کو ضم کر سکتے ہیں۔ اس کے ساتھ ساتھ، دور کے طاق زیادہ آہستہ آہستہ متاثر ہو سکتے ہیں۔ اس قسم کی آبادی والے ای اے سیلولر ای اے (سی ای اے) یا سیلولر جینیٹک الگورتھم (سی جی اے) کے نام سے بھی مشہور ہیں۔ آبادی کے افراد کو ترتیب دینے کے لیے عام طور پر استعمال ہونے والا ڈھانچہ 2 ڈی ٹورائڈل گرڈ ہے، حالانکہ طول و عرض کی تعداد کو آسانی سے بڑھایا جا سکتا ہے (3 ڈی تک) یا کم کیا جا سکتا ہے (1 ڈی تک، مثال کے طور پر۔ ایک انگوٹھی، دائیں طرف کی شکل دیکھیں)۔ گرڈ میں کسی خاص فرد کے پڑوس کی تعریف اس سے آبادی میں دوسروں کے درمیان مین ہیٹن کے فاصلے کے لحاظ سے کی جاتی ہے۔ بنیادی الگورتھم میں، تمام محلوں کا سائز اور شکلیں ایک جیسی ہوتی ہیں۔ دو جہتی سی ای اے کے لیے دو سب سے زیادہ استعمال ہونے والے محلے ایل 5 اور سی 9 ہیں، بائیں طرف کی شکل دیکھیں۔ یہاں، L کا مطلب لکیری ہے جبکہ C کا مطلب کمپیکٹ ہے۔ ہر ڈیم ایک پینمیکٹک ذیلی آبادی کی نمائندگی کرتا ہے جس کے اندر ساتھی کا انتخاب اور اولاد کی قبولیت والدین کی جگہ لے کر ہوتی ہے۔ اولاد کی قبولیت کے قوانین مقامی نوعیت کے ہوتے ہیں اور پڑوس پر مبنی ہوتے ہیں: مثال کے طور پر، یہ واضح کیا جا سکتا ہے کہ بہترین اولاد والدین کی جگہ لینے سے بہتر ہونی چاہیے یا، کم سختی سے، صرف بدترین فرد سے بہتر ہونی چاہیے۔ پہلا قاعدہ اشرافیہ ہے اور دوسرے غیر اشرافیہ اصول کے مقابلے میں زیادہ انتخابی دباؤ پیدا کرتا ہے۔ اشرافیہ پسند ای اے میں، آبادی کا بہترین فرد ہمیشہ زندہ رہتا ہے۔ اس سلسلے میں، وہ حیاتیاتی ماڈل سے ہٹ جاتے ہیں۔ محلوں کا اوورلیپ پڑوس کی حدود میں جینیاتی معلومات کے زیادہ تر سست پھیلاؤ کا سبب بنتا ہے، لہذا اس کا نام پھیلاؤ ماڈل ہے۔ ایک بہتر اولاد کو اب آبادی میں پھیلنے کے لیے پینمیکسی سے زیادہ نسلوں کی ضرورت ہے۔ یہ مقامی طاقوں کے ظہور اور ان کے مقامی ارتقاء کو فروغ دیتا ہے، اس طرح طویل عرصے تک جینو ٹائپک تنوع کو محفوظ رکھتا ہے۔ نتیجہ دوڑ کے دوران تلاش کی جگہ کے مطابق ڈھالنے والی چوڑائی اور گہرائی کی تلاش کے درمیان ایک بہتر اور متحرک توازن ہے۔ گہرائی کی تلاش طاق کی حدود میں طاق اور چوڑائی کی تلاش میں اور پوری آبادی کے مختلف طاقوں کے ارتقا کے ذریعے ہوتی ہے۔ اسی پڑوس کے سائز کے لیے، جینیاتی معلومات کا پھیلاؤ ایل 9 جیسے لمبے اعداد و شمار کے لیے سی 9 جیسے بلاک کے مقابلے میں بڑا ہوتا ہے، اور پھر رنگ کے مقابلے میں نمایاں طور پر بڑا ہوتا ہے۔ اس کا مطلب یہ ہے کہ رنگ کے پڑوس اعلی معیار کے نتائج حاصل کرنے کے لیے اچھی طرح سے موزوں ہیں، چاہے اس کے لیے نسبتا طویل مدت درکار ہو۔ دوسری طرف، اگر کوئی بنیادی طور پر تیز اور اچھے، لیکن ممکنہ طور پر سب آپٹیمل نتائج میں دلچسپی رکھتا ہے، تو 2 ڈی ٹوپولوجیز زیادہ موزوں ہیں۔ موازنہ آبادی کے دونوں ماڈلز کو جینیاتی الگورتھم، ارتقائی حکمت عملی اور دیگر ای اے پر لاگو کرتے وقت، کل آبادی کو ذیلی آبادی میں تقسیم کرنے سے عام طور پر قبل از وقت انضمام کا خطرہ کم ہو جاتا ہے اور مجموعی طور پر بہتر نتائج کی طرف جاتا ہے جو کہ پینمیکٹک ای اے کے ساتھ توقع سے زیادہ قابل اعتماد اور تیز ہوتا ہے۔ پڑوس کے ماڈلز کے مقابلے میں جزیرے کے ماڈلز کا نقصان یہ ہے کہ وہ بڑی تعداد میں نئے حکمت عملی کے پیرامیٹرز متعارف کراتے ہیں۔ ادب میں اس موضوع پر موجودہ مطالعات کے باوجود، صارف کے لیے ناموافق ترتیبات کا ایک خاص خطرہ باقی رہتا ہے۔ پڑوس کے ماڈلز کے ساتھ، دوسری طرف، صرف پڑوس کے سائز کی وضاحت کرنی پڑتی ہے اور، دو جہتی ماڈل کے معاملے میں، پڑوس کے اعداد و شمار کا انتخاب شامل کیا جاتا ہے۔ متوازی چونکہ آبادی کے دونوں ماڈل آبادی کی تقسیم کا اشارہ دیتے ہیں، اس لیے وہ ای اے کو متوازی بنانے کی بنیاد کے طور پر اچھی طرح سے موزوں ہیں۔ یہ سیلولر ای اے پر اور بھی زیادہ لاگو ہوتا ہے، کیونکہ وہ صرف اپنے متعلقہ ڈیمس کے اراکین کے بارے میں مقامی طور پر دستیاب معلومات پر انحصار کرتے ہیں۔ اس طرح، انتہائی صورت حال میں، ہر فرد کو ایک آزاد عمل درآمد دھاگہ تفویض کیا جا سکتا ہے، تاکہ پورا سی ای اے متوازی ہارڈ ویئر پلیٹ فارم پر چل سکے۔ جزیرے کا ماڈل متوازی کی بھی حمایت کرتا ہے، مثال کے طور پر۔ ہر جزیرے کو ایک پروسیسر تفویض کرکے۔ اگر جزائر کی ذیلی آبادی کو پینمیکٹک طور پر منظم کیا جائے تو ایک نسل کی اولاد کے تمام جائزوں کو اضافی طور پر متوازی بنایا جا سکتا ہے۔ حقیقی دنیا کی ایپلی کیشنز میں تشخیص عام طور پر اب تک کا سب سے زیادہ وقت طلب حصہ ہوتا ہے۔ یقینا، جزیرے کی ذیلی آبادی کو سی ای اے کے طور پر ڈیزائن کرنا بھی ممکن ہے، تاکہ سی ای اے کو متوازی بنانے کے بارے میں پہلے دیے گئے بیانات لاگو ہوں۔ اس طرح، مناسب متوازی کے ساتھ درجہ بندی آبادی کے ڈھانچے بنائے جا سکتے ہیں۔ متوازی بنانے کے لیے نہ صرف نسبتا مہنگے کمپیوٹر کلسٹر بلکہ سستے گرافکس کارڈ (جی پی یو) بھی استعمال کیے جا سکتے ہیں۔ تاہم، اس بات پر زور دینا ضروری ہے کہ سی ای اے، یا جزیروں میں پھیلی آبادی کے ساتھ ای اے، ایک سرچ ماڈل کی نمائندگی کرتے ہیں جو روایتی ای اے سے کئی طریقوں سے مختلف ہے۔ مزید برآں، وہ ترتیب وار اور متوازی دونوں پلیٹ فارمز پر چل سکتے ہیں، جو اس حقیقت کو اجاگر کرتا ہے کہ ماڈل اور نفاذ دو مختلف تصورات ہیں۔ کتابچہ ایرک کینٹو-پاز (2001): موثر اور درست متوازی جینیاتی الگورتھم (پی ایچ ڈی مقالہ، یونیورسٹی آف الینوائے، اربانا-شیمپین، یو ایس اے)۔ سپرنگر، نیویارک، نیویارک۔ مارٹینا گورجز-شلیئٹر (1990): جینیاتی الگورتھم اور آبادی کے ڈھانچے-ایک بڑے پیمانے پر متوازی الگورتھم۔ پی ایچ ڈی مقالہ، یونیورسٹی ڈورٹمنڈ، فیکلٹی فار انفارمیٹک، جرمنی۔ اینریک البا، برنابے ڈورونسورو (2008): سیلولر جینیاتی الگورتھم۔ سپرنگر، نیویارک، نیویارک۔ ڈیرک سدولٹ (2015): متوازی ارتقاء الگورتھم۔ جانوس کاپرزیک میں، وٹولڈ پیڈریکس (ایڈز۔ ): متوازی ارتقاء الگورتھم۔ سپرنگر، برلن، ہیڈلبرگ، پی پی۔ 929-959 گیبریل لیوک، اینریک البا (2011): متوازی جینیاتی الگورتھم۔ سپرنگر، برلن ہیڈلبرگ۔ سیلولر آٹومیٹن ڈوئل فیز ارتقاء ارتقاء الگورتھم میٹا ہیورسٹک حوالہ جات ارتقاء الگورتھم بھی دیکھیں۔