The Problem of the Multidimensional Investor's Portfolio Using Nature-Inspired Algorithms - Review Article

Al-Thanoon, Niam

doi:10.33899/iqjoss.2021.0169970

Journals List

The Problem of the Multidimensional Investor's Portfolio Using Nature-Inspired Algorithms - Review Article

IRAQI JOURNAL OF STATISTICAL SCIENCES

Article 5, Volume 18, Issue 2, 2021, Pages 30-40 PDF (1.72 M)

Document Type: Review Paper

DOI: 10.33899/iqjoss.2021.0169970

Author

Niam Al-Thanoon^*

Department of Operations Research and Intelligent Techniques, Faculty of Computer Science and Mathematics, University of Mosul, Mosul, Iraq

Abstract

The backpack problem or the multidimensional investor is an important and well-known hard (discontinuous) constrained combinatorial optimization problem in operations research and optimization. Nowadays, algorithms inspired by nature have become extremely important in solving many mathematical problems, including the problem of the investor's portfolio. In order to reach the best solutions, in this research, three algorithms were used to solve this problem. The marine predator algorithm, which is a very modern algorithm, outperformed the weed algorithm and the black hole algorithm in obtaining the best solution and the least possible time. While the black hole algorithm came in the third place, although it does not need to specify any parameter of the algorithm before its work.

Highlights

تعتبر مسألة حقیبة الظهر أو المستثمر متعدد الأبعاد من مسائل الأمثلیة التوافقیة الصعبة (المتقطعة ) المقیدة المهمة والمعروفة جدا فی بحوث العملیات والأمثلیة . ولغرض الوصول الى افضل الحلول تم فی هذا البحث استعراض ثلاثة خوارزمیات استخدمت فی حل هذه المسائلة. اذ تفوقت خوارزمیة المفترسات البحریة وهی خوارزمیة حدیثة جدا على خوارزمیة الاعشاب الضارة وخوارزمیة الثقب الاسود فی الحصول على افضل احل وباقل وقت ممکن. فی حین جاءت خوارزمیة الثقب الاسود فی المرتبة الثالثة على الرغم من انها لا تحتاج الى تحدید ای معلمة بالخوارزمیة قبل عملها.

Keywords

Investor bag; weed algorithm; marine predator algorithm; black hole algorithm

Full Text

المقدمة Introduction

مسألة الأمثلیة التوافقیة (Combinatorial optimization problem) هی دراسة ریاضیة لإیجاد الحل الأمثل من مجموعة محدودة finite من الکائنات أو الأشیاء أو الأهداف (objects) . تأتی شعبیة مسائل الأمثلیة التوافقیة من حقیقة أن دالة الهدف والقیود فی العدید من مسائل العالم الحقیقی لها طبیعة مختلفة (غیر خطیة ، وغیر تحلیلیة ، الخ) ، بینما یکون فضاء البحث محدود finite . فی مثل هذه المسائل ، تکون الطرق الدقیقة أو المضبوطة غیر عملیة فی إیجاد الحل الأمثل لأن وقت التنفیذ یزداد أسیا" أو بازدیاد أسیا" increasing exponentially مع حجم المسألة. لذلک ، أصبح الاهتمام بتطبیق الخوارزمیات المستوحاة من الطبیعة أمرًا ضروریًا لحل هذه المسائل والحصول على النتائج فی وقت معقول. تعتبر مسألة حقیبة الظهر أو المستثمر متعدد الأبعاد (MKP) (Multidimensional Knapsack Problem) من مسائل الأمثلیة التوافقیة الصعبة (المتقطعة ) المقیدة المهمة والمعروفة جدا فی بحوث العملیات والأمثلیة وهی أیضًا مسألة (NP-hard combinatorial or complete problem) حتى فی حالة وجود قید واحد فقط بسبب صعوبة أیجاد وقت متعدد الحدود (polynomial time) لمعالجتها واستخدمت أیضا على نطاق واسع کمسائل benchmark التوافقیة للخوارزمیات التطوریة (Bhattacharjee & Sarmah, 2015; Haddar, Khemakhem, Hanafi, & Wilbaut, 2015; He, Xie, Wong, & Wang, 2018; Jianjun Liu, Wu, Cao, Wang, & Teo, 2016; Patvardhan, Bansal, & Srivastav, 2015) .إنها القضیة المهمة فی فئة أو صنف مسألة حقیبة المستثمر (Knapsack Problem) (KP) و تمثل عضوا فی عائلة Knapsack أی أنها التعمیم لمسألة 0–1 knapsack المعروفة أو الأساسیة التی لها قید واحد (m=1) بمعنى ان(MKP) لها(m˃1) من القیود. لقد حظیت هذه المسألة باهتمام واسع من قبل فئة أو جالیة(مجموعة أو جماعة) بحوث العملیات خلال العقود الأخیرة الماضیة . مسألة حقیبة الظهر أو المستثمر متعدد الأبعاد لها تطبیقات واسعة فی مجالات الهندسة والعلوم والإدارة حیث یمکن صیاغة التطبیقات العملیة المتنوعة کـ (MKP) أو لمسألة حقیبة الظهر أو المستثمر متعدد الأبعاد مثل الموازنة الرأسمالیة- استثماریة (وضع الموازنة أو أعداد الموازنة الکبیرة أو الرئیسیة )(capital budgeting) ، مسألة اختیار المحفظة الاستثماریة (portfolio selection problem) ، تحمیل الشحنة أو الحمولة أو البضائع (cargo loading) ، تخصیص الموارد (resource allocating)،اختیار المشروع (project selection) ، أسهم القطع أو الأوراق المالیة القطع cutting stock ، تخصیص قواعد البیانات والمعالجات فی معالجة البیانات الموزعة ، وجدولة برامج الکمبیوتر فی بیئة متعدد البرامج (multiprogramming environment) ، وسیاسة الاستثمار لقطاع السیاحة فی البلدان النامیة ، مسألة جدولة الصور الیومیة لأقمار مراقبة الأرض الصناعیة PSOT-5 الخ . فی الدراسات المبکرة أو الحدیثة ، تم تطبیق عدة طرق لحل مسألة حقیبة المستثمر متعدد الأبعاد والتی تقسم الى فئتین ، الخوارزمیات الدقیقة أو المضبوطة أو تم استخدام الخوارزمیات التحدیدیة (Deterministic Algorithms) لحل مسألة MKP ذات small-scale ، مثل خوارزمیة القطع والتحدید (Branch and Bound Algorithm) وخوارزمیة التراجع (Backtracking Algorithm) وکذلک تم استخدام طریقة البرمجة الدینامیکیة (Dynamic Programming) عن طریق تجزئة مسألة حقیبة الظهر أو المستثمر الأصلیة الى مجموعة من مسائل حقیبة الظهر أو المستثمر الأصلیة. أیضا استخدمت استراتیجیة البحث متعددة المستویات (Multi-level Search Strategy) لحل مسألة حقیبة الظهر أو المستثمر ذات المقیاس العالی (large-scale MKP) حیث تأخذ هذه الاستراتیجیة بنظر الاعتبار التکالیف المنخفضة للمتغیرات غیر الأساسیة فی حل الإرخاء(relaxation) لمسألة البرمجة الخطیة وخوارزمیة أخرى التی تدمج بین البرمجة الخطیة و (Tabu Search) الکفوءة . لکن مع زیادة عدد الوحدات والقیود یزداد الوقت المستهلک للخوارزمیة التحدیدیة بشدة لحل هذه المسائل .لهذا السبب یتم استخدام الفئة الثانیة المتمثلة بالخوارزمیات غیر التحدیدیة (Nondeterministic Algorithms) التی تتضمن الخوارزمیات العشوائیة (Randomized Algorithms) ، خوارزمیة التقریب (Approximation Algorithm) والخوارزمیات التطوریة (Evolutionary Algorithms) لحل هذه المسألة . نظرًا لخاصیة NP-hardness الموجودة فی مسألة حقیبة الظهر أو المستثمر متعدد الأبعاد ، فان حل هذه المسالة لایزال یمثل تحدیا مثیرا للاهتمام خاصة عندما یزداد عدد القیود . لذا فإن الطرق الدقیقة أو التحدیدیة تؤدی أداءً ضعیفًا أو بشکل سیئ عندما تکون المقاییس أو الأحجام کبیرة large scales لمسألة حقیبة المستثمر، على الرغم من أنها یمکن أن تعطی الحلول المثلى فی حل المسائل الصغیرة الحجم او صغیرة المقیاس small-scale problems.

مسألة أو مشکلة حقیبة الظهر أو المستثمر متعدد الأبعاد (Multidimensional 0–1 Knapsack Problem) (MKP)

تعتبر مسألة حقیبة المستثمر متعدد الأبعاد 0-1 الأبعاد (MKP) (Multidimensional 0-1 Knapsack Problem) واحدة من اکثر مسائل البرمجة الصحیحة المقیدة المعروفة او المشهورة ذات معاملات عدم السالبیة وهی حالة خاصة من البرامج الخطیة العامة 0-1 وتمثل التعمیم لمسألة حقیبة الظهر المعروفة 0-1 التی لها قید واحد (m=1). مسألة حقیبة الظهر أو المستثمر متعدد الأبعاد من مسائل الأمثلیة التوافقیة الصعبة (المتقطعة ) المقیدة المهمة والمعروفة جدا فی بحوث العملیات والأمثلیة (NP-hard combinatorial or complete problem) حتى فی حالة وجود قید واحد فقط بسبب صعوبة أیجاد وقت متعدد الحدود (polynomial time) لمعالجتها . تعتبر MKP نموذجًا لتخصیص الموارد . نفترض ان لدینا فی مسألة حقیبة المستثمر متعدد الأبعاد مجموعة J من n من الأهداف أو الأشیاء (objects) وحقیبة المستثمر ذات m من الأبعاد ، کل هدف له ربح (الربح للوحدة jth ) والوزن فی البعد i حیث أن ای أن کل وحدة تتطلب أو تحتاج وحدات من أستهلاک الموارد ، کل بعد من أبعاد الحقیبة له السعةcapacity) ) أو القدرة . الهدف من مسألة حقیبة الظهر أو المستثمر متعدد الأبعاد هو تعظیم الربح الکلی للوحدات المعطاة المختارة مع تحقق جمیع قیود الموارد أی أیجاد المجموعة جزئیة من جمیع الوحدات لتکون مختارة فی الحقیبة ( أختیار مجموعة جزئیة من العناصر أو الکائنات المعطاة) مع تعظیم الربح الکلی (دالة الهدف الخطیة) للعناصر المختارة بحیث لا تتجاوز سعة أو قدرة کل بعد أو أبعاد الحقیبة (قیود القدرة أو السعة الخطیة) وتحقق جمیع أو مجموعة من قیود حقیبة المستثمر knapsack . یجب أن یکون مجموع الأوزان للأهداف أو الأشیاء المضمنة فی کل بعد اقل أو یساوی . بإدخال المتغیرات الثنائیة للإشارة فیما اذا کان الهدف أو الشئ او الغرض j متضمن فی الحقیبة أو غیر متضمن . نفترض أن جمیع المعلمات موجبة . ریاضیا، یمکن صیاغة مسألة حقیبة الظهر او المستثمر متعدد الأبعاد کما یلی :

حیث أن هی المتجه 0-1 ذو البعد n . متغیر القرار الثنائی ، اذا وفقط اذا کانت الوحدة jth معبأة أو مختارة فی حقیبة المستثمر وأن اذا کانت الوحدة jth غیر معبأة أو مختارة فی حقیبة المستثمر. n تمثل عدد جمیع الوحدات و m تمثل عدد القیود لحقیبة المستثمر. تمثل الربح للوحدة jth . تمثل السعة أو القدرة للقید ith (قید الموارد) والأستهلاک للوحدة jth . تمثل الوزن أو الکلفة للوحدة jth على القید أو حقیبة المستثمر ith (أستهلاک موارد للوحدة jth للبعد ith لحقیبة المستثمر). لعدم خسارة العمومیة ، نفترض أن المعاملات العددیة غیر السالبة:

الخوارزمیات المستوحاة من الطبیعة (Nature-Inspired Optimization Algorithms)

فی العقود الأخیرة ، ظهرت العدید من خوارزمیات الأمثلیة المستوحاة من الطبیعة الحدسیة المطورة والتی لها القدرة بکفاءة على حل المسائل الصعبة والمعقدة من مسائل العالم الحقیقی وخاصة مسائل الأمثلیة. من الأمثلة على هذه الخوارزمیات ، خوارزمیة الثقب الأسود أو المظلم (Black Hole Algorithm) خوارزمیة البحث الجذبیة (Gravitational search Algorithm) وخوارزمیة (Multiverse Algorithm) وغیرها. نظرًا لطبیعة الظاهرة ، نجد أن العدید من هذه الخوارزمیات تعمل فی مساحات بحث مستمرة ویجب تکییفها لحل مسألة حقیبة الظهر أو المستثمر متعدد الأبعاد . یجب أن تضمن عملیة التکیف الحفاظ على آلیات الاستغلال والاستکشاف بحیث یتم الحفاظ على کفاءة الخوارزمیة. فی مثل هذه المسائل ، لا توجد أو لیس هناک خوارزمیة فعالة لحل جمیع حالاتها أو جمیع الحالات الخاصة بها. تحتاج مسألة أو مشکلة حقیبة الظهر أو المستثمر متعدد الأبعاد إلى طرق أو خوارزمیات بدیلة فعالة وکفوءة لأن الطرق الدقیقة أو الخوارزمیات التحدیدیة عادة لا یمکنها التعامل مع الحجم الکبیر (large-scale) لهذه المسائل ذات الأبعاد العالیة عندما یزداد التعقید الزمنی تصاعدیا مع حجم المسألة . فی الأدبیات هناک أعمال منشورة ترکز بشکل أساسی على استخدام الخوارزمیات المستوحاة من الطبیعة بشکل واسع وأثبتت هذه الخوارزمیات بنجاح کفاءتها وأنها أکثر فاعلیة وتنتج الحل القریب من الأمثل بوقت معقول فی حل مسائل الأمثلیة التوافقیة خاصة مسألة حقیبة المستثمر متعدد الأبعاد . الخوارزمیات المستوحاة من الطبیعة هی خوارزمیات تصادفیة أو عشوائیة مستوحاة من سلوک الأنواع المختلفة فی الطبیعة. تتکون کل خوارزمیة مستوحاة من الطبیعة من مجموعة من المجتمع الأبتدائی أو الحلول الأولیة ، ثم یتم أختبار متتالیة أو سلسلة من الحلول خطوة بخطوة بناءً على العشوائیة وبعض القواعد المحددة للوصول إلى الحل الأمثل. تتمتع هذه الخوارزمیات بالقدرة على التعامل مع العدید من مشکلات التحسین نظرًا لبساطتها ومرونتها

الهدف من هذا البحث هو التحقیق أو الأثبات فی فعالیة الخوارزمیات الفوق الحدسیة المستوحاة من الطبیعة عند التعامل مع مسألة الأمثلیة التوافقیة مثل مشکلة حقیبة الظهر أو المستثمر متعدد الأبعاد 0-1.

3.1 خوارزمیة الثقب الاسود (black hole algorithm)

فی السنوات الأخیرة أصبح الإهتمام متزاید بتصمیم وتطویر خوارزمیات التحسین المستوحاة من الطبیعة، وتعد خوارزمیة الثقب الأسود(BHA) Black Hole Algorithm واحدة من أحدث الخوارزمیات المستوحاة من الطبیعة وأکثرها شیوعاً وتعود إلى (Hatamlou, 2013)، تحاکی خوارزمیة BHA ظاهرة فیزیائیة وهی ظاهرة الثقب الأسود فی الفضاء لحل مشاکل التحسین من خلال البحث فی مساحة المشکلة بطریقة فعالة وبسیطة للغایة، ویتطلب عددًا أقل من المعلمات ووقت أقل، والثقب الأسود هو أحد أغرب الأجسام الموجودة فی الفضاء الخارجی وأکثرها روعة وهو جسم شدید الکثافة مع إمتلاکه لجاذبیة قویة، ولأول مرة فی عام 1967 أطلق العالم الفیزیائی الأمریکی John Wheeler على ظاهرة إنهیار الکتلة أسم الثقب الأسود، حیث یتشکل الثقب الأسود فی الفضاء عندما ینهار نجم کبیر الحجم وقوة الجاذبیة للثقب الأسود تکون عالیة جداً لدرجة أنه حتى الضوء لایستطیع الهروب منه، وتکون الجاذبیة قویة جداً لأن المادة قد ضغطت فی مساحة صغیرة وأی شیء یعبر حدود الثقب الأسود سیبتلعه ویتلاشى ولا یمکن أن یبتعد عن قوته الهائلة، وتعرف الحدود الکرویة للثقب الأسود فی الفضاء بأفق الحدث ویطلق على نصف قطر أفق الحدث نصف قطرSchwarzschild عند هذا الشعاع تکون سرعة الهروب مساویة لسرعة الضوء وبمجرد مرور الضوء لایمکنه الهروب، أی بمعنى أخر انه لایمکن لأی شیء أن یهرب من داخل أفق الحدث لأنه لاشیء یمکن أن یکون أسرع من الضوء ویطلق علیه أسود لأنه یمتص کل الضوء ولایعکس شیئاً، والمخطط التالی یوضح الثقب الأسود وأفق الحدث ونصف قطر الافق والنجوم التی حوله (Elnaz Pashaei & Aydin, 2017b). والخطوات أدناه توضح طریقة محاکاة BHA من ظاهرة الثقب الأسود (Kumar, Datta, & Singh, 2015) و (Qasim, Al-Thanoon, & Algamal, 2020):

الخطوة الأولى: تبدأ خوارزمیة الثقب الأسود المقترحة (BHA) بمجموعة أولیة عشوائیة من الحلول المرشحة النجوم (Stars) فی مساحة البحث لمشکلة معینة ویتشکل الثقب الأسود فی الفضاء الحقیقی عن طریق إنهیار النجوم الفردیة ثم تتطور لإیجاد الحل الأمثل ودالة موضوعیة (دالة اللیاقة) یتم حسابها لکل نجم وفی کل تکرار من BHA یتم إختیار أفضل مرشح فی المجتمع بعد تقییم قیم دالة اللیاقة بإختیار أفضل قیمة لیاقة لیکون هو الثقب الأسود والباقی یشکل النجوم العادیة.

الخطوة الثانیة: بعد عملیة التهیئة تطور خوارزمیة BHA الحلول المرشحة نحو الحل الأمثل عبر آلیة بسیطة حیث یبدأ الثقب الأسود (المرشح الأفضل) فی جذب النجوم (المرشحة الأخرى) من حوله حیث تبدأ جمیع النجوم بالتحرک نحو الثقب الأسود وعندما یقترب نجم جداً من الثقب الأسود فسیبتلعه الثقب الأسود ویختفی الى الأبد وفی مثل هذه الحالة یتم إنشاء نجم جدید (حل مرشح) بشکل عشوائی ووضعه فی مساحة البحث ویبدأ بحثاً جدیداً، ویتم حساب الحل المحدث کما فی الصیغة التالیة (Hatamlou, 2017; Jiefang Liu, Chung, & Wang, 2018; Elnaz Pashaei & Aydin, 2017a; E. Pashaei, Pashaei, & Aydin, 2019):

(2)

حیث أن: و : تمثل مواقع النجم فی التکرارات t و t +1 ، على التوالی. : هو موقع الثقب الأسود فی مساحة البحث. rand :هو رقم عشوائی ضمن التوزیع المنتظم [0 ، 1]. N: هو إجمالی عدد النجوم (مرشح حلول).

الخطوة الثالثة: یُعرف المجال المحیط بالثقب الأسود فی الفضاء الخارجی بأفق الحدث، ویسمى نصف قطر أفق الحدث Schwarzschild radius. توضح الدائرة الحمراء فی المخطط (2-1) أفق أحداث الثقب الأسود، فی الفضاء الحقیقی یتم حساب نصف قطر Schwarzschild وفق الصیغة التالیة:

(3)

حیث تشیر M و G و C إلى کتلة الثقب الأسود وثابت الجاذبیة وسرعة الضوء على التوالی.

وفی BHA یتم حسابه وفق الصیغة التالیة :

(4)

حیث أن: : تمثل قیمة لیاقة الثقب الأسود. : تمثل قیمة لیاقة کل نجم. N: هو عدد النجوم (الحلول المرشحة).

الخطوة الرابعة: بسبب الکثافة الشدیدة والجاذبیة القویة للثقب الأسود عندما یعبر النجم أفق الحدث ، سیبتلعه الثقب الأسود ویختفی وفی منطقة أفق الحدث تکون سرعة الهروب مساویة لسرعة الضوء لذلک لا یمکن لأی شیء الابتعاد عن أفق الحدث. فی BHA یتم حساب المسافة الإقلیدیة بین الثقب الأسود والنجم فإذا کانت هذه المسافة أقل من نصف قطر Schwarzschild ، فاستبدل بنجم جدید فی الموقع العشوائی فی مساحة البحث.

الخطوة الخامسة: فی BHA إذا وصل النجم إلى موقع بتکلفة أقل من الثقب الأسود فی هذه الحالة یجب إستبدال مواقعهم.

3.2 خوارزمیة الاعشاب الضارة

خوارزمیة أمثلة الأعشاب الضارة Invasive Weed Optimization Algorithm (IWO)هی خوارزمیة التحسین العشوائی العددی المستوحات بیولوجیا من الأعشاب الضارة والتی اقترحت لاول مرة من قبل Mehrabian و Lucas فی عام (2006 م) . وهذه الخوارزمیة ببساطة تحاکی السلوک الطبیعی للأعشاب الضارة فی الاستعمار وایجاد مکان مناسب للنمو والتکاثر. لمحاکاة السلوک الاستعماری للأعشاب الضارة یجب ان تؤخذ بعض الخصائص الاساسیة لهذه العملیة بنظر الاعتبار(Jayabarathi, Yazdani, & Ramesh, 2012; Josinski, Kostrzewa, Michalczuk, & Switonski, 2014; Niknamfar & Niaki, 2018; Panda, Dutta, & Pradhan, 2017) :

1. یتم نشر عدد محدود من البذور على منطقة البحث (تهیئة عدد السکان ).

2. کل البذور تنمو الى نباتات مزهرة وتنتج البذور اعتمادا على دالة اللیاقة ( التکاثر).

3. البذور المنتجة یتم نشرها عشوائیا على منطقة البحث لتنمو وتصبح نباتات جدیدة ( التشتت المکانی)

4. تستمر هذه العملیة الى ان یتم الوصول الى الحد الأقصى من عدد النباتات.

وفقط النباتات ذات دالة اللیاقة العالیة یمکنها البقاء على قید الحیاة وإنتاج البذور, ویجری القضاء على الاخرین (الإقصاء التنافسی). تستمر العملیة الى ان یتم الوصول الى الحد الأقصى من التکرارات على امل ان النبات الذی یحمل أفضل دالة لیاقه سیکون هو الاقرب الى الحل الامثل

تتضمن خوارزمیة أمثلة الأعشاب الضارة(IWO) عدد من الخطوات الاساسیة, هذه الخطوات مترابطة مع بعضها البعض ولا یمکن تطبیق هذه الخوارزمیة على ای مسالة مالم تطبق هذه الخطوات جمیعها والا ستفقد خوارزمیة أمثلة الأعشاب الضارة (IWO) قیمتها وفائدتها فی ایجاد وتحسین الحل, ویمکن توضیح خطوات الخوارزمیة على النحو الاتی

الخطوة الاولى: تهیئة المجتمع الابتدائی Initialize A Population یتم تولید مجتمع ابتدائی من الحلول ونشرها على d من الابعاد من مساحة المشکلة مع مواقع عشوائیة وحساب قیمة دالة اللیاقة لهذه المجتمع.

الخطوة الثانیة: التکاثر Reproduction

یسمح للنبات فی مجتمع النباتات بإنتاج البذور seed (التکاثر) وذلک اعتمادا على قیمة دالة اللیاقة الخاصة به وکذلک الحد الأعلى و الأدنى لدالة اللیاقة فی المستعمرة, اذ یزداد عدد البذور التی ینتجها النبات خطیا من الحد الأدنى الممکن لإنتاج البذور الى أقصى حد ممکن , وبعبارة اخرى فان النبات ینتج البذور اعتمادا على قیمة دالة اللیاقه الخاصة به واقل دالة لیاقه للمستعمرة واعلى دالة لیاقة للمستعمرة وذلک للتاکد من ان الزیادة تکون خطیة

المعادلة ادناه توضح عملیة التکاثر للأعشاب الضارة :

(4)

حیث ان Floor تدل على ان البذور تقرب لاقرب عدد صحیح، تمثل دالة اللیاقه ل i من الأعشاب الضارة، : تمثل الحد الأقصى والأدنى لقیمة دالة اللیاقة فی لمستعمرة وان تمثل الحد الأقصى والأدنى لعدد البذور التی سوف تنتج فی المستعمرة.

تمثل الصیغة اعلاه العلاقة الریاضیة بین عدد البذور وقیمة دالة اللیاقة للأعشاب الضارة اذ ینخفض عدد البذور مع زیادة قیمة دالة اللیاقة وعدد البذور یتراوح بین ال و . تعتبر الأفراد القابلة للتکاثر هی تلک الأفراد ذوات أفضل قیمة لدالة اللیاقة من الأفراد غیر الملائمة للاستخدام وتعنی کلمة "أفضل" هنا هی ان لهذه الأفراد فرصة اکبر للبقاء على قید الحیاة والتکاثر . لذا لایسمح للأفراد غیر الملائمة للاستخدام بالتکاثر. ومع ذلک فان وجهة النظر هذه تتجاهل شیء مهما الا وهو ان الخوارزمیة التطوریة هی طریقة احتمالیة وتکراریة , فمن الممکن ان بعض الأفراد غیر الملائمة للاستعمال تحمل فی داخلها معلومات اکثر فائدة من الأفراد الملائمة خلال عملیة التطور . علاوة على ذلک غالبا ما یستطیع النظام الوصول الى النقطة المثلى اذا کان بالامکان عبور المنطقة غیر قابلة للتطبیق (وخاصة فی فضاء البحث غیر المحدب). لذا اقترحت تقنیة التکاثر اعلاه لاعطاء فرصة اکبر للأفراد غیر الملائمة للاستخدام للبقاء على قید الحیاة , وهذه العملیة مماثلة للآلیة التی تحدث فی الطبیعة.

الخطوة الثالثة: التشتت المکانی Spatial Dispersal

توفر هذه الخطوة لخوارزمیة الأعشاب الضارة خاصیتی العشوائیة والتکیف, اذ یتم توزیع البذور المتولدة عشوائیا على d من الابعاد فی فضاء البحث بواسطة ارقام عشوائیة تتوزع توزیعا طبیعیا بمعدل (μ=0) وتباین متغیر. وهذا یعنی ان البذور سیتم توزیعها عشوائیا بحیث انها تقع بالقرب من النبات الام. الا ان الانحراف المعیاری Standard deviation (SD) (σ) للدالة العشوائیة سیخفض من قیمة اولیة محددة مسبقا الى قیمة نهائیة فی کل خطوة (کل جیل), من خلال المعادلة التالیة:

(5)

اذ ان یمثل الانحراف المعیاری فی الخطوة الحالیة، یمثل الحد الأقصى من التکرارات، وان n یمثل معدل التاشیر اللاخطی. یضمن هذا التحویل ان احتمالیة اسقاط البذور فی منطقة بعیدة ینخفض بشکل غیر خطی فی کل خطوة زمنیة مما یؤدی الى تجمیع النباتات المجربة وازالة النباتات غیر الملائمة. یتم حساب موقع البذور الجدیدة باستخدام المعادلة التالیة:

(6)

حیث ان یمثل موقع الذریة وان یمثل موقع الابا، فی حین Random یمثل تولید اعداد عشوائیة من التوزیع الطبیعی القیاسی محصورة ضمن الفترة [0,1] .

الخطوة الرابعة: الإقصاء التنافسی Competitive Exclusion

إذا کان النبات لایترک أی نسل فسوف ینقرض من الوجود, لذا دعت الحاجة الى نوع من التنافس بین النباتات للحد من العدد الأقصى من النباتات فی المستعمرة . بعد مرور بعض التکرارات فان عدد النباتات فی المستعمرة تصل الى الحد الأقصى عن طریق التکاثر السریع ومع ذلک فمن المتوقع ان یتم استنساخ النباتات المجربة اکثر من النباتات غیر الملائمة . عند الوصول الى الحد الأقصى لعدد النباتات فی المستعمرة P_max فسوف تنشط آالیة إقصاءالنباتات ذات دالة اللیاقة الضعیفة لذلک الجیل. اذ تعمل آلیة الإقصاء على النحو التالی: عندما یتم الوصول الى الحد الأقصى لعدد الأعشاب فی المستعمرةیسمح لکل عشب بإنتاج البذور وذلک وفقا للآلیة المذکورة فی الخطوة (2) (التکاثر), ثم یتم السماح للبذور المنتجة بالإنتشار فی منطقة البحث وذلک وفقا للخطوة (3) (التشتت المکانی). عندما تجد جمیع البذور مواقعها فی منطقة البحث یتم ترتیبها مع آبائها (کمستعمرة من الأعشاب الضارة). بعد ذلک یتم القضاء على الأعشاب الضارة ذات دالة اللیاقة المنخفضة للوصول الى الحد الأقصى المسموح به للمجتمع فی المستعمرة . وبهذه الطریقة ترتب النباتات وذریتها معا والعنصر ذو أفضل دالة لیاقة سینجو ویبقى على قید الحیاة مع السماح لعملیة التکرار داخل الخوارزمیة . وکما ذکر سابقا فی الخطوة (2) فإن هذه الآلیة تعطی فرصة للنباتات ذات دالة اللیاقة المنخفضة لإعادة الإنتاج فإن کانت ذریتها ذات دالة لیاقة جیدة فی المستعمرة فستنجو وتبقى على قید الحیاة بعبارة اخرى لایتم إقصائها. وتطبق آلیة التحکم بالمجتمع على الذریة ایضاً لحین إنتهاء مرحلة معینة مما یحقق الإقصاء التنافسی.

3.3 خوارزمیة المفترسات البحریة

تعد خوارزمیة المفترسات البحریة وتکتب اختصارا (MPA) من أحدث خوارزمیات الأمثلیة فوق الحدسیة الکفوءة المستوحاة من الطبیعة وتنتمی الى فئة الخوارزمیات المستوحاة بایولوجیا .تم أقتراح هذه الخوارزمیة فی عام (2020) من قبل مجموعة من الباحثین (Afshin Faramarzi ,Mohammad Heidarinejad,Seyedali Mirjalili,Amir H.Gandommi ) (Abd Elaziz et al., 2020; Abdel-Basset, El-Shahat, Chakrabortty, & Ryan, 2021; Abdel-Basset, Mohamed, Chakrabortty, Ryan, & Mirjalili, 2021; Elaziz et al., 2020; Faramarzi, Heidarinejad, Mirjalili, & Gandomi, 2020). أن الألهام الرئیسی لخوارزمیة المفترسات البحریة هو أستراتیجیة البحث الشاملة للکائنات البحریة (المفترسات)فی البحث عن الفریسة وهی حرکات لیفی والحرکة البروانیة فی المحیطات الى جانب سیاسة معدل المواجهة المثلى فی التفاعل البایولوجی بین المفترس والفریسة . تتبع خوارزمیة المفترسة البحریة (MAP) القواعد التی تتحکم بشکل طبیعی فی أستراتیجیة البحث الأمثل التی تواجه معدل المواجهة بین المفترس والفریسة فی النظم البیئیة البحریة . نوضح الوصف الریاضی لهذه الخوارزمیة. على غرار معظم الخصائص الوصفیة فأن خوارزمیة المفترسات البحریة هی طریقة تعتمد على المجتمع ، حیث أن الحل الأولی أو الأبتدائی یتوزع توزیع منتظم فی فضاء البحث کما فی الصیغة الأولیة التالیة:

(7)

حیث ان هما الحد الأدنى والأعلى للمتغیرات و rand هو متجه عشوائی منتظم فی الفترة من[0,1]. بناءً على نظریة البقاء للأصلح ، یُقال أن الحیوانات المفترسة العلیا فی الطبیعة هی أکثر موهبة فی البحث عن الطعام. وبالتالی ، یتم ترشیح الحل الأنسب کأفضل مفترس لبناء مصفوفة تسمى النخبة (Elite) . ترتیبات هذه المصفوفة فی البحث عن الفریسة وایجادها بناءً على المعلومات الخاصة بمواقع الفریسة.

حیث یمثل متجه المفترس الأعلى ، والذی یتم تکراره N من المرات لبناء مصفوفة النخبة . N هو عدد وکلاء البحث بینما d هو عدد الأبعاد .

من الملاحظ أن کلاً من المفترس والفریسة یعتبران وکلاء البحث لأنه بحلول الوقت الذی یبحث فیه المفترس عن فریسته ، تبحث الفریسة عن طعامها الخاص وفی نهایة کل تکرار ، سیتم تحدیث مصفوفة النخبة إذا تم استبدال المفترس الأعلى بالمفترس الأفضل . مصفوفة أخرى بنفس أبعاد النخبة تسمى الفریسة (Prey) والتی یقوم فیهاالمفترسون بتحدیث مواقعهم بناءً علیها . بعبارة أخرة التهیئة یُنشئ التهیئة الفریسة الأولیة التی فیها الأصلح أو اللیاقة للمفترس یکون النخبة . تظهر مصفوفة الفریسة على النحو التالی:

حیث أن الذی یمثل البعد jth للفریسة ith . وتجدر الإشارة إلى أن العملیة الکاملة للأمثلیة بأکملها مرتبطة بشکل أساسی ومباشر بهاتین المصفوفتین.

تنقسم عملیة تحسین خوارزمیة المفترسات البحریة MPA)) إلى ثلاث مراحل رئیسیة من التحسین مع مراعاة نسبة السرعة المختلفة وفی نفس الوقت محاکاة الحیاة الکاملة للحیوان المفترس والفریسة. تستخدم المفترسات البحریة حرکة لیفی والحرکة البراونیة التی تعتمدها الکائنات البحریة أثناء الأفتراس کآلیات بحث مثلى وکلاهما یعتمد على أستراتیجیات عشوائیة. یتم أستخدام نسبة السرعة للفریسة الى المفترس لأجراء مفاضلة بین استراتیجیات لیفی والبراونیة. عندما تکون صغیرة أی تساوی (0.1) فأن أفضل استراتیجیة للمفترس هی التحرک بخطوات لیفی (مرحلة الاستکشاف) بغض النظر عما اذا کانت الفریسة تتحرک فی البراونیة أو لیفی . اذا کانت فأن أفضل طریقة للمفترس هی التحرک بالخطوات البراونیة اذا کانت الفریسة تتحرک فی خطوات لیفی . عندما تکون ، یجب أن لا یتحرک المفترس مطلقا بغض النظر عما اذا کانت الفریسة تتحرک فی البراونیة أو لیفی لأن الفریسة ستأتی فی حد ذاتها (مرحلة الأستغلال) .

تنقسم عملیة الأمثلیة لخوارزمیة المفترسات البحریة الى ثلاث مراحل رئیسیة مع مراعاة نسبة السرعة المختلفة وفی نفس الوقت محاکاة الحیاة الکاملة للمفترس والفریسة

المرحلة الاولى: مرحلة الأستکشاف (نسبة أو معدل السرعة العالیة)

فی معدل السرعة العالیة أو عندما یتحرک المفترس أسرع من الفریسة یحدث هذا السیناریو فی التکرارات الأولیة للأمثلیة ، حیث یکون الاستکشاف مهماً. بالنسبة لمعدل السرعة العالیة ، فإن أفضل استراتیجیة للحیوان المفترس لا یتحرک على الإطلاق. ویتم تطبیق النموذج الریاضی لهذه القاعدة على النحو التالی:

(10)

حیث ان عبارة عن متجه یحتوی على أرقام عشوائیة بناءً على التوزیع الطبیعی الذی یمثل الحرکة البراونیة. یظهر الترمیز کرونکر عملیة الضرب (entry-wise) للعناصر.

المرحلة الثانیة: الأنتقال بین الأستکشاف والأستغلال (نسبة أو معدل سرعة الوحدة)

فی معدل سرعة الوحدة أو عندما یتحرک کل من المفترس والفریسة فی نفس الوتیرة أی أن ، فإنه یحاکی على أن کلاهما یبحث عن فریسته. ویحدث هذا فی المرحلة المتوسطة من الأمثلیة حیث یحاول الاستکشاف أن یکون عابراً أو أنتقالیا للاستغلال. فی هذه المرحلة ، یکون کل من الاستکشاف والاستغلال مهمان ، وبالتالی ، یتم تعیین أو تخصیص نصف المجتمع للاستکشاف والنصف الآخر للاستغلال. وفی هذه الحالة تکون الفریسة هی المسؤولة عن الاستغلال والمفترس للاستکشاف. أستناداً الى هذه القاعدة ، فی نسبة او معدل سرعة الوحدة إذا تحرکت الفریسة فی لیفی ، فإن أفضل استراتیجیة للمفترس هی البراونیة. فان حرکات الفریسة فی لیفی بینما یتحرک المفترس فی الحرکة البراونیة.

بینما للنصف الأول من المجتمع فأن:

(11)

حیث أن هو متجه للأرقام العشوائیة المستندة على توزیع لیفی الذی یمثل حرکة لیفی. والمضروب من و یحاکی حرکة الفریسة بطریقة لیفی مع إضافة حجم الخطوة إلى موقع الفریسة الذی یحاکی حرکة الفریسة.

نظرًا لأن معظم حجم خطوةلتوزیع لیفی یرتبط بخطوات صغیرة ، فأن هذه الحالة تساعد فی الاستغلال وبالنسبة للنصف الثانی من المجتمع :

(12)

حیث أن

معلمة تکیفیة للتحکم فی حجم الخطوة لحرکة المفترس. یحاکی ضرب و حرکة المفترس بالطریقة براونیة بینما تقوم الفریسة بتحدیث موقعها بناءً على حرکة الحیوانات المفترسة فی الحرکة البراونیة.

المرحلة الثالثة: مرحلة الأستغلال (نسبة أو معدل السرعة المنخفضة)

فی معدل السرعة المنخفضة أو عندما یتحرک المفترس أسرع من الفریسة. یحدث هذا السیناریو فی المرحلة الأخیرة من عملیة الأمثلیة والتی ترتبط فی الغالب بقدرة عالیة على الاستغلال. فی معدل السرعة المنخفضة فإن أفضل استراتیجیة للمفترس هی لیفی ویتم تحویل مرحلة الأستکشاف الى مرحلة الأستغلال عندما تکون ویتم تمثیل هذه المرحلة على النحو التالی:

(13)

الضرب لـ و التی تحاکی حرکة المفترس فی إستراتیجیة لیفی بینما إضافة حجم الخطوة إلى موقع (Elite) تحاکی حرکة المفترس للمساعدة فی تحدیث موقع الفریسة.

النتائج والمناقشة

لغرض استعراض استخدام الخوارزمیات الثلاثة المذکورة فی متن البحث تم استخدام خمسة امثلة مختلفة الحجم والسعة تمثل حقیبة المستثمر وحسب الجدول 1.

جدول 1: یوضح امثلة حقیبة المستثمر

Instance	dimension	capacity M	weights w	profits c
Mkp-1	4	20	w={6 5 9 7}	c={9 11 13 15}
Mkp-2	4	11	w={2 4 6 7}	c={6 10 12 13}
Mkp-3	10	269	w={95 4 60 32 23 72 80 62 65 46}	c={55 10 47 5 4 50 8 61 85 87}
Mkp-4	15	375	w={56.358531 80.874050 47.987304 89.596240 74.660482 85.894345 51.353496 1.498459 36.445204 16.589862 44.569231 0.466933 37.788018 57.118442 60.716575}	c={0.125126 19.330424 58.500931 35.029145 82.284005 17.410810 71.050142 30.399487 9.140294 14.731285 98.852504 11.908322 0.891140 53.166295 60.176397}
Mkp-5	23	10000	w={983 982 981 980 979 978 488 976 972 486 486 972 972 485 485 969 966 483 964 963 961 958 959}	c={981 980 979 978 977 976 487 974 970 485 485 970 970 484 484 976 974 482 962 961 959 958 857}

ولغرض تسلیط الضوء على اسلوب عمل الخوارزمیات الموضحة بالجانب النظری تم تلخیص النتائج وعرضها فی الجدولین 2 و 3. حیث تم تکرار کل خوارزمیة 30 مرة. من خلال ملاحظة هذه النتائج یتضح من الجدول 2 بان جمیع الخوارزمیات حصلت على نفس النتائج فیما یخص الحصول على افضل حل وافضل ربح. فی حین نلاحظ من نتائج الجدول 3 بان خوارزمیة المفترسات حققت اقل عدد من التکرارات للوصول الى الحل الامثل مقارنة بخوارزمیة القب الاسود وخوارزمیة الاعشاب الضارة. کذلک تم ملاحظة بان خوارزمیة الاعشاب الضارة اعطت نتائج افضل من خوارزمیة الثقب الاسود وهذا قد یعود الى امکانیة الخوارزمیة فی البحث عن الحلول افضل مقارنة بخوارزمیة الثقب الاسود على الرغم من ان خوارزمیة الثقب الاسود لا تحتاج الى معلمات اولیة فی عمل الخوارزمیة مقارنة بالخوارزمیتین الاخیریتین.

جدول 2: نتائج الخوارزمیات فیما یخص افضل حل

Instance	Methods	Total profit	Total weight	Best
Mkp-1	BHA	35	18	35
	IWO	35	18	35
	MPA	35	18	35
Mkp-2	BHA	23	11	23
	IWO	23	11	23
	MPA	23	11	23
Mkp-3	BHA	295	269	295
	IWO	295	269	295
	MPA	295	269	295
Mkp-4	BHA	481.0694	354.9608	481.07
	IWO	481.0694	354.9608	481.07
	MPA	481.0694	354.9608	481.07
Mkp-5	BHA	9767	9768	9767
	IWO	9767	9768	9767
	MPA	9767	9768	9767

جدول 3: نتائج الخوارزمیات حسب عدد التکرارات والحل الامثل.

Instance	Methods	Mean iterations	solution vector
Mkp-1	BHA	1	1101
	IWO	1	1101
	MPA	1	1101
Mkp-2	BHA	1	0101
	IWO	1	0101
	MPA	1	0101
Mkp-3	BHA	5.12	0111000111
	IWO	4.63	0111000111
	MPA	3.41	0111000111
Mkp-4	BHA	1	001010110111011
	IWO	1	001010110111011
	MPA	1	001010110111011
Mkp-5	BHA	6.92	11111111010000011000000
	IWO	5.66	11111111010000011000000
	MPA	4.85	11111111010000011000000

الاستنتاجات

References

1- Abd Elaziz, M., Shehabeldeen, T. A., Elsheikh, A. H., Zhou, J., Ewees, A. A., & Al-qaness, M. A. A. (2020). Utilization of Random Vector Functional Link integrated with Marine Predators Algorithm for tensile behavior prediction of dissimilar friction stir welded aluminum alloy joints. Journal of Materials Research and Technology, 9(5), 11370-11381. doi:10.1016/j.jmrt.2020.08.022

2- Abdel-Basset, M., El-Shahat, D., Chakrabortty, R. K., & Ryan, M. (2021). Parameter estimation of photovoltaic models using an improved marine predators algorithm. Energy Conversion and Management, 227. doi:10.1016/j.enconman.2020.113491

3- Abdel-Basset, M., Mohamed, R., Chakrabortty, R. K., Ryan, M., & Mirjalili, S. (2021). New binary marine predators optimization algorithms for 0–1 knapsack problems. Computers & Industrial Engineering, 151. doi:10.1016/j.cie.2020.106949

4- Bhattacharjee, K. K., & Sarmah, S. P. (2015). A binary firefly algorithm for knapsack problems. Paper presented at the 2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM).

5- Elaziz, M. A., Ewees, A. A., Yousri, D., Alwerfali, H. S. N., Awad, Q. A., Lu, S., & Al-Qaness, M. A. A. (2020). An Improved Marine Predators Algorithm With Fuzzy Entropy for Multi-Level Thresholding: Real World Example of COVID-19 CT Image Segmentation. IEEE Access, 8, 125306-125330. doi:10.1109/ACCESS.2020.3007928

6- Faramarzi, A., Heidarinejad, M., Mirjalili, S., & Gandomi, A. H. (2020). Marine Predators Algorithm: A nature-inspired metaheuristic. Expert Systems with Applications, 152. doi:10.1016/j.eswa.2020.113377

7- Haddar, B., Khemakhem, M., Hanafi, S., & Wilbaut, C. (2015). A hybrid heuristic for the 0–1 Knapsack Sharing Problem. Expert Systems with Applications, 42(10), 4653-4666. doi:10.1016/j.eswa.2015.01.049

8- Hatamlou, A. (2013). "Black hole: A new heuristic optimization approach for data clustering". Information sciences, 222, 175-184.

9- Hatamlou, A. (2017). Solving travelling salesman problem using black hole algorithm. Soft Computing, 22(24), 8167-8175. doi:10.1007/s00500-017-2760-y

10- He, Y., Xie, H., Wong, T.-L., & Wang, X. (2018). A novel binary artificial bee colony algorithm for the set-union knapsack problem. Future Generation Computer Systems, 78, 77-86. doi:10.1016/j.future.2017.05.044

11- Jayabarathi, T., Yazdani, A., & Ramesh, V. (2012). Application of the invasive weed optimization algorithm to economic dispatch problems. Frontiers in Energy, 6(3), 255-259. doi:10.1007/s11708-012-0202-1

12- Josinski, H., Kostrzewa, D., Michalczuk, A., & Switonski, A. (2014). The expanded invasive weed optimization metaheuristic for solving continuous and discrete optimization problems. ScientificWorldJournal, 2014, 831691. doi:10.1155/2014/831691

13- Kumar, S., Datta, D., & Singh, S. K. (2015). "Black hole algorithm and its applications" Computational intelligence applications in modeling and control (pp. 147-170): Springer.

14- Liu, J., Chung, F.-L., & Wang, S. (2018). Black Hole Entropic Fuzzy Clustering. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 48(9), 1622-1636. doi:10.1109/tsmc.2017.2682883

15- Liu, J., Wu, C., Cao, J., Wang, X., & Teo, K. L. (2016). A Binary differential search algorithm for the 0–1 multidimensional knapsack problem. Applied Mathematical Modelling, 40(23-24), 9788-9805. doi:10.1016/j.apm.2016.06.002

16- Niknamfar, A. H., & Niaki, S. T. A. (2018). A binary-continuous invasive weed optimization algorithm for a vendor selection problem. Knowledge-Based Systems, 140, 158-172. doi:10.1016/j.knosys.2017.11.004

17- Panda, M. R., Dutta, S., & Pradhan, S. (2017). Hybridizing Invasive Weed Optimization with Firefly Algorithm for Multi-Robot Motion Planning. Arabian Journal for Science and Engineering, 43(8), 4029-4039. doi:10.1007/s13369-017-2794-6

18- Pashaei, E., & Aydin, N. (2017a). Binary black hole algorithm for feature selection and classification on biological data. Applied Soft Computing, 56, 94-106. doi:10.1016/j.asoc.2017.03.002

19- Pashaei, E., & Aydin, N. (2017b). "Binary black hole algorithm for feature selection and classification on biological data". Applied Soft Computing, 56, 94-106.

20- Pashaei, E., Pashaei, E., & Aydin, N. (2019). Gene selection using hybrid binary black hole algorithm and modified binary particle swarm optimization. Genomics, 111(4), 669-686. doi:10.1016/j.ygeno.2018.04.004

21- Patvardhan, C., Bansal, S., & Srivastav, A. (2015). Solving the 0–1 Quadratic Knapsack Problem with a competitive Quantum Inspired Evolutionary Algorithm. Journal of Computational and Applied Mathematics, 285, 86-99. doi:10.1016/j.cam.2015.02.016

22- Qasim, O. S., Al-Thanoon, N. A., & Algamal, Z. Y. (2020). Feature selection based on chaotic binary black hole algorithm for data classification. Chemometrics and Intelligent Laboratory Systems, 204, 104104.

Statistics

Article View: 511

PDF Download: 415