تعیین پیت بهینه با الگوریتم کوروبوف اصلاح‌شده

1- مقدمه

اندکی پس از طرح الگوریتم کوروبوف در۱۹۷۴[1] مشخص شد که این روش امکان تعیین محدوده بهینه در تمام حالات را ندارد. با توجه به سادگی کدنویسی و پیاده‌سازی این الگوریتم، ابداع‌کنندگان به کار روی آن ادامه دادند تا در ۱۹۹۲ الگوریتم کوروبوف اصلاح شده (Corrected Form of Korobov Algorithm) معرفی شد [2].
دقت کنید که خیلی پیش از این -یعنی در ۱۹۶۵- الگوریتم گراف سه‌بعدی لرچس-گروسمن با یک روش تحقیق در عملیاتی قابل اثبات مبتنی بر نظریه گراف مسئله طراحی محدوده نهایی بهینه را حل کرده بود [3]. با این حال به دلایل مختلفی همچون سرعت اجرا، دشواری کدنویسی و ضعف در پیاد‌ه‌سازی شیب‌های متغیر، کار روی توسعه روش‌های حل مسئله تعیین محدوده نهایی ادامه یافت [4]. این ضعف‌ها امروزه تا حد زیادی رفع گردیده‌اند اما جای پرسش است که چرا کار روی توسعه یک روش تعیین محدوده نهایی کارآمد هنوز هم ادامه دارد.
یک پاسخ این است که خود مسئله تعیین محدوده نهایی تا این زمان هنوز به طور جامع مدل نشده است و از این رو تمام روش‌های توسعه یافته برای حل مسأله با مدل کنونی به نوعی باز و ناتمام تلقی می‌شوند. در رایج ترین نگاه، این مسئله به صورت مجزا و به صورت مسئله استخراج کاواکی با ارزش بیشینه اقتصادی مطرح می‌شود. این در حالی است که این مدل گویای حقیقت مسئله نیست. تمام بلوک‌های یک مدل در یک زمان استخراج نمی‌شوند و لذا باید ارزش اقتصادی تنزیل شده برای استخراج آن‌ها در نظر گرفته شود؛ حال آنکه ارزش اقتصادی تنزیل شده تنها در صورتی قابل محاسبه است که شما پیش از آن محدوده نهایی و توالی استخراج را به دست آورده باشید. پس مسئله در یک دور ناتمام می‌افتد [5]:
«محدوده کاواک با بالاترین ارزش خالص فعلی (NPV) قابل تعیین نیست مگر آن که ارزش بلوک‌ها مشخص باشد؛ ارزش بلوک‌ها قابل تعیین نیست مگر آن که توالی استخراج مشخص شده باشد و توالی استخراج قابل تعیین نیست مگر آن که محدوده کاواک معین شده باشد».
برای رفع این مشکل رویکردهای دیگری به مدلسازی و حل این مسئله مانند روش پارامتری کردن توسعه داده شده‌اند که نارسایی‌های خود را دارند. با توجه به این که هنوز هیچ یک از این مدل‌ها به طور کامل رد یا پذیرفته نشده‌اند پس الگوریتم‌های حل این مدل‌ها نیز به صورت موازی پیش می‌روند.

2- ماهیت نظری الگوریتم کوروبوف اصلاح شده

الگوریتم کوروبوف در مواردی که مخروط‌های استخراجی دارای بلوک‌های مشترک باشند، گاه برای ارزیابی دچار خطا می‌شود. کوروبوف اصلاح شده برای رفع خطای الگوریتم اصلی کوروبوف یک قانون ساده اما کارآمد دارد:
«اگر دو یا چند مخروط دارای بلوک‌های مشترک باشند، تخصیص ابتدا باید به بلوک‌های غیرمشترک صورت پذیرد و تخصیص بلوک‌های مشترک تنها زمانی انجام می‌شود که تمام مقادیر منفی بلوک‌های غیرمشترک صفر شده باشد».
نکته بسیار مهم در فهم این شیوه این است که ماهیت نظری و اجرای عملی آن اندکی متفاوت است. اابداع‌کنندگان در مقاله سال ۱۹۹۲ در شرح ماهیت نظری این الگوریتم و رفتاری که در حالت آرمانی باید از خود نشان می‌دهد از نمودار موجود در شکل 1 استفاده کرده‌اند. در این شکل برای خلاصه‌سازی Ci نماد مخروطی است که روی i اُامین بلوک مثبت در طبقه مورد بررسی تشکیل می‌شود. بر این اساس ماهیت نظری الگوریتم به این صورت است که هر بار یک ترکیب به ترتیب از میان گروه‌های زیر انتخاب می‌شود ( ابتدا C1 بعد C2 بعد C1&C2 بعد C3 و …) و بعد در هر موردی که بلوک مشترک در مخروط آن ترکیب وجود داشت، ابتدا تخصیص به بلوک‌های غیرمشترک و سپس به بلوک‌های مشترک صورت می‌پذیرد. اگر در پایان این فرآیند ارزش مخروط همچنان مثبت بود، مخروط به پاسخ اضافه می‌شود و در غیر این صورت پس از بازگرداندن مقادیر اصلی به بلوک‌ها، جستجو به سراغ ترکیب دیگری می‌رود.

شکل ۱- چگونگی ترکیب و ترتیب بررسی گروه‌های مخروط استخراجی در الگوریتم کوروبوف اصلاح شده

این کامل‌ترین نوع جستجو است که البته بدیهی است که در واقعیت نه انجام آن ضروری و نه در تمام موارد ممکن است. در مدل‌های کوچک دوبعدی می‌توان این روش را برای آموزش مفهوم الگوریتم به کار گرفت اما بررسی تمام ترکیب‌های ممکن در یک مدل بلوکی بزرگ باعث کاهش کارایی به لحاظ مصرف حافظه و زمان‌بری می‌شود. پس ابداع‌کنندگان یک راهکار عملی برای اجرای این الگوریتم معرفی کردند که توسط آن بسیاری از ترکیب‌های ممکن پیش از بررسی عملا حذف شوند. در این روش در هر طبقه الگوریتم کوروبوف اصلی تا جایی اجرا می‌شودکه ارزش یک بلوک مثبت پس از تخصیص، مثبت باقی بماند. در این نقطه اجرای الگوریتم متفاوت می‌شود و به جای استخراج این بلوک، این موضوع بررسی می‌شود که آیا در مخروط مربوط به آن، بلوکی وجود دارد که توسط مخروط مجاوری از قبل مقداردهی شده باشد یا خیر. اگر این طور نباشد که آن بلوک مثبت و مخروط آن خیلی ساده به جواب بهینه اضافه می‌شوند و اجرای الگوریتم کوروبوف در آن طبقه ادامه می‌یابد. اما اگر این طور باشد (یعنی بلوک مشترکی با یک مخروط مجاور یافت شود) در این صورت فرآیندی به نام بازتخصیص انجام می‌شود و تنها در صورتی که پس از این فرآیند، ارزش بلوک مورد نظر هنوز مثبت باشد مخروط استخراجی آن و تمام مخروط‌هایی که با این مخروط بلوک مشترک دارند، استخراج می‌شوند.
دقت کنید که در این شیوه، اجرای الگوریتم اصلاح شده تنها در پایان جستجوی یک طبقه مقادیر بلوک‌ها به حالت نخست بازمی‌گردد و جستجو از طبقه بعد ادامه می‌یابد (برخلاف الگوریتم کوروبوف که با استخراج یک بلوک مثبت و مخروط آن، ارزش‌ها به حالت اول بازمی‌گشتند و جستجو از آخرین بلوک مثبت ناکام قبلی از سرگرفته می‌شود)؛ پس در هیچ حالت دیگری جز تغییر طبقه، مقادیر به حالت اولیه بازنمی‌گردند.
روش اجرای الگوریتم در قالب یک روندنما در مقاله سال ۱۹۹۳ ابداع‌کنندگان آورده شده است. با توجه به اهمیت این روندنما در ادامه به توضیح گام به گام آن می‌پردازیم.

زمینو در زمینه  الگوریتم‌های کوروبوف آموزش منتشر کرده است :

الگوریتم‌های کوروبوف در تعیین محدوده نهایی کاواک 

3- روش اجرای الگوریتم کوروبوف اصلاح شده
مراحل اجرای الگوریتم کوروبوف اصلاح شده بر اساس روندنمای شکل ۲ به صورت زیر خلاصه می‌شود:
۱- از طبقه اول کار را شروع کن (K=1).
۲- در طبقه مورد نظر الگوریتم کوروبوف را اجرا کن اما به محض این که به یک بلوک مثبت رسیدی که پس از تخصیص، مقدار آن هنوز مثبت باقی مانده است توقف کن و بند ۳ را بررسی کن.
۳- آیا مخروط این بلوک تهی است؟ اگر این طور است آن بلوک را به جواب بهینه اضافه کن. اگر این طور نیست به بند ۴ برو.
۴- آیا درمخروط مربوط به این بلوک مثبت، هیچ بلوکی وجود دارد که توسط یک مخروط مجاور از قبل مقداردهی شده باشد؟ اگر این طور است فرآیند بازتخصیص1 را اجرا کن. اگر این طور نیست همان مخروط را به پاسخ بهینه اضافه کن. فرآیند بازتخصیص در بخش4 توضیح داده می‌شود.
۵- در صورت نیاز به اجرای فرآیند بازتخصیص، اگر بعد از اجرا، بلوک مثبت همچنان مثبت بود، ابتدا تمام بلوک‌های مثبت خارجی که در مقداردهی به این مخروط به نوعی سهیم هستند را همراه مخروطشان به جواب اضافه کن و سپس خود بلوک مثبتی را که این مخروط را تشکیل داده و مخروط آن را نیز به جواب اضافه کن. در غیر این صورت -یعنی اگر بعد یا در حین بازتخصیص ارزش بلوک صفر شد- بدون تغییر مقادیر بلوک‌ها، جستجو برای بلوک‌های مثبت بعدی در طبقه مورد نظر را ادامه بده. این بند بعد از بررسی مثال بخش ۵ برایتان روشن خواهد شد.
۶- پس رسیدن به انتهای یک طبقه به طبقه بعد برو و البته پیش از هر کاری نخست تمام مقادیر بلوک‌ها در مدل را به حالت اول برگردان و از گام ۲ کار را از سر بگیر تا جایی که به آخرین طبقه برسی.

شکل ۲- روندنمای الگوریتم کوروبوف اصلاح شده

برای درک بهتر مفهوم بازتخصیص و الگوریتم‌های کوروبوف به بسته آموزشی «الگوریتم‌های Korobov در تعیین محدوده نهایی کاواک» مراجعه کنید.
موضوع مهم در مورد الگوریتم کوروبوف اصلاح شده، معرفی نادرست آن در داخل کشور است. این الگوریتم قادر به تعیین محدوده نهایی بهینه می‌باشد و این در حالی است که نخستین معرفی‌کنندگان روش در داخل کشور با یک برداشت اشتباه از الگوریتم آن را در زمره الگوریتم‌های ناتوان در تعیین پیت بهینه دسته‌بندی کرده‌اند.
در آموزش پیش‌گفته برای نخستین بار با بررسی دقیق مقالات اصلی و بحث با پروفسور Dowd یکی از ابداع‌کنندگان الگوریتم، ماهیت صحیح این الگوریتم را استخراج و آموزش داده است.

فهرست منابع

[1] David. M., Dowd, P.A. and Korobov S., 1974, Forecasting departure from panning in open pit design and grade control. In 12^th Symposium on the application of computers and operaton research in the mineral industries (APCOM) volume 2 (Golden, Colo: Colorado School of Mines), F131-42.

[2] Dowd, P.A. and Onur A.H., 1992, Optimising open pit design and sequencing. In 23^rd Symposium on the application of computers and operaton research in the mineral industries (APCOM) (Littleton, Colorado: AIME), pp. 411-22.

[3] Lerchs, H., Grossmann, I., 1965, Optimum design of open-pit mines, CIM Bulletin, pp. 58 17–24.

[4] Dowd, P.A., Onur, A.H., 1993, Open pit optimization – part 1: optimal open pit design, Trans. Instn Min. Metall,102, pp. A95-A104.

[5] Whittle J,, 1989, The facts and fallacies of open pit optimization. Whittle Programming Pty., Ltd., North Balwyn, Victoria, Australia.

از همین نویسنده در زمینو منتشر شده است

الگوریتم GEP در تابع یابی هوشمند

روش NATM در ساخت تونل

درباره نویسنده

مصطفی آصفی

مصطفی آصفی از بنیان‌گذاران مجموعه‌های آموزشی زمینو و هم‌رویش مستقر در پارک علم و فناوری استان همدان است…+