Iterated local search
آئی ٹیریٹڈ لوکل سرچ (آئی ایل ایس) اطلاقی ریاضی اور کمپیوٹر سائنس میں ایک اصطلاح ہے جو مجرد اصلاح کے مسائل کو حل کرنے کے لیے مقامی تلاش یا پہاڑی چڑھائی کے طریقوں میں ترمیم کی وضاحت کرتی ہے۔ مقامی تلاش کے طریقے مقامی کم از کم میں پھنس سکتے ہیں، جہاں کوئی بہتر پڑوسی دستیاب نہیں ہے۔ ایک سادہ ترمیم مقامی تلاش کے معمول پر کالوں کو دہرانے پر مشتمل ہوتی ہے، ہر بار مختلف ابتدائی ترتیب سے شروع ہوتی ہے۔ اسے بار بار مقامی تلاش کہا جاتا ہے، اور اس کا مطلب یہ ہے کہ پچھلے مقامی تلاش کے مراحل کے دوران حاصل کردہ علم استعمال نہیں ہوتا ہے۔ سیکھنے سے یہ ظاہر ہوتا ہے کہ پچھلی تاریخ، مثال کے طور پر پہلے پائے جانے والے مقامی منیما کے بارے میں میموری، مقامی تلاش کے لیے بہتر اور بہتر ابتدائی نکات پیدا کرنے کے لیے کان کنی کی جاتی ہے۔ مضمر مفروضہ مقامی منیما کی کلسٹرڈ تقسیم کا ہے: جب کسی فنکشن کو کم سے کم کیا جاتا ہے، تو اچھے مقامی منیما کا تعین کرنا آسان ہوتا ہے جب مقامی کم سے کم سے کم قیمت کے ساتھ شروع کیا جاتا ہے اس کے مقابلے میں جب بے ترتیب نقطہ سے شروع ہوتا ہے۔ واحد انتباہ یہ ہے کہ دی گئی کشش کے طاس میں قید سے بچنا ہے، تاکہ اگلی دوڑ کے لیے مقامی منی مائیزر کو ابتدائی مقام میں تبدیل کرنے کے لیے کک مناسب طور پر مضبوط ہونی چاہیے، لیکن میموری سے کم بے ترتیب دوبارہ شروع ہونے سے بچنے کے لیے زیادہ مضبوط نہ ہو۔ تکرار شدہ مقامی تلاش مقامی طور پر بہترین حل کی ترتیب بنانے پر مبنی ہے: موجودہ مقامی کم از کم کو پریشان کرنا ؛ ترمیم شدہ حل سے شروع کرنے کے بعد مقامی تلاش کا اطلاق کرنا۔ خلل ڈالنے کی طاقت کو ایک مختلف پرکشش طاس کی طرف لے جانے کے لیے کافی ہونا چاہیے جو ایک مختلف مقامی زیادہ سے زیادہ کی طرف لے جائے۔ پرٹربیشن الگورتھم آئی ایل ایس کے لیے پرٹربیشن الگورتھم تلاش کرنا کوئی آسان کام نہیں ہے۔ بنیادی مقصد ایک ہی مقامی کم از کم پر پھنسنا نہیں ہے اور اس پراپرٹی کو یقینی بنانے کے لیے، انڈو آپریشن ممنوع ہے۔ اس کے باوجود، ایک اچھی ترتیب کو بہت سی اقدار پر غور کرنا پڑتا ہے، کیونکہ دو قسم کی خراب ترتیبات موجود ہیں: بہت کمزور: ایک ہی مقامی کم از کم بہت مضبوط پر واپس آنا: بے ترتیب دوبارہ شروع کریں بینچ مارک پرٹربیشن یہ طریقہ کار پرٹربیشن کے لیے متعدد اقدار کو طے کرنے پر مشتمل ہوتا ہے تاکہ یہ اقدار مثال کے طور پر اہم ہوں: اوسط امکان پر اور نایاب نہیں۔ اس کے بعد، رن ٹائم پر بینچ مارک پلاٹ کو چیک کرنا ممکن ہوگا تاکہ منظور شدہ مثالوں کے بارے میں اوسط اندازہ حاصل کیا جا سکے۔ چونکہ کوئی ترجیحی فنکشن نہیں ہے جو یہ بتاتا ہے کہ کسی دی گئی رکاوٹ کے لیے کون سا سب سے موزوں قدر ہے، اس لیے بہترین معیار یہ ہے کہ اسے موافقت پذیر بنایا جائے۔ مثال کے طور پر بٹٹی اور پروٹاسی نے میکس-سیٹ کے لیے ایک رد عمل تلاش الگورتھم کی تجویز پیش کی جو آئی ایل ایس فریم ورک میں بالکل فٹ بیٹھتا ہے۔ وہ ایک "ڈائریکٹڈ" پرٹربیشن اسکیم انجام دیتے ہیں جسے تبو سرچ الگورتھم کے ذریعے نافذ کیا جاتا ہے اور ہر پرٹربیشن کے بعد وہ ایک معیاری لوکل ڈیسنٹ الگورتھم کا اطلاق کرتے ہیں۔ خلل کو اپنانے کا ایک اور طریقہ یہ ہے کہ تلاش کے دوران اس کی طاقت کو تعیناتی طور پر تبدیل کیا جائے۔ پرٹربیشن کو بہتر بنانا ایک اور طریقہ کار یہ ہے کہ مسئلہ کے ذیلی حصے کو بہتر بنایا جائے جبکہ غیر غیر فعال پراپرٹی کو فعال رکھا جائے۔ اگر یہ طریقہ کار ممکن ہے، تو پریشانیوں کے بعد پیدا ہونے والے تمام حل بہت اچھے ہوتے ہیں۔ مزید برآں نئے حصوں کو بھی بہتر بنایا گیا ہے۔ ایپلی کیشنز اس طریقہ کار کا اطلاق کئی مشترکہ اصلاحاتی مسائل پر کیا گیا ہے جن میں جاب شاپ شیڈولنگ کے مسائل، فلو شاپ کے مسائل، وہیکل روٹنگ کے مسائل کے ساتھ ساتھ بہت سے دوسرے بھی شامل ہیں۔ حوالہ جات آپٹیمائزیشن الگورتھم اور طریقے