Introducing a new meta-heuristic algorithm to solve the feature selection problem

Subject Areas : Futurology

Mehdi Khadem ¹ , Abbas Toloie Eshlaghy ^{2 *} , Kiamars Fathi Hafshejani ³

1 - Department of Industrial Management, Science and Research Branch, Islamic Azad University, Tehran, Iran.
2 - Department of Industrial Management, Science and Research Branch, Islamic Azad University, Tehran, Iran.
3 - Department of Industrial Management, South Tehran Branch, Islamic Azad University, Tehran, Iran

Received: 2020-09-25 Accepted : 2022-02-27 Published : 2022-11-22

Keywords: Meta-Heuristic Algorithm, Particle Swarm Algorithm, Qashqai Algorithm, Feature Selection Problem, Genetic algorithm,

Abstract :

Due to the increase in the volume of data and information in recent years, the issue of choosing the most appropriate feature for decision making has become very important. Classic attribute selection methods cannot work well on big data. Because feature selection is a complex problem, it seems appropriate to use meta-heuristic algorithms to solve this problem. In this paper, a new meta-heuristic algorithm inspired by nomadic migration to solve the feature selection problem is presented. This algorithm is named in honor of the Qashqai tribe. In this hybrid algorithm, the proportional function was designed based on the feature selection algorithm and based on minimizing the number of features and the amount of data error using neural network results. Then the Qashqai meta-heuristic algorithm was implemented on this fitness function and the results were compared with the well-known meta-heuristic algorithms of genetics and particle swarm. The results of the hypothesis test showed that the Qashqai optimization algorithm to solve the feature selection problem by the genetic algorithm and particle swarm is not defeated and in terms of convergence to the optimal solution works well.

References:

-

Due to the increase in the volume of data and information in recent years, the issue of choosing the most appropriate feature for decision making has become very important. Classic attribute selection methods cannot work well on big data. Because feature selection is a complex problem, it seems appropriate to use meta-heuristic algorithms to solve this problem. In this paper, a new meta-heuristic algorithm inspired by nomadic migration to solve the feature selection problem is presented. This algorithm is named in honor of the Qashqai tribe. In this hybrid algorithm, the proportional function was designed based on the feature selection algorithm and based on minimizing the number of features and the amount of data error using neural network results. Then the Qashqai meta-heuristic algorithm was implemented on this fitness function and the results were compared with the well-known meta-heuristic algorithms of genetics and particle swarm. The results of the hypothesis test showed that the Qashqai optimization algorithm to solve the feature selection problem by the genetic algorithm and particle swarm is not defeated and in terms of convergence to the optimal solution works well.

Full-Text:



        

 

ارائه الگوریتم فرا ابتکاری جدید جهت حل مساله انتخاب ویژگی

 

 

چکیده                        

با توجه به افزایش حجم داده ها و اطلاعات در سالهای اخیر مساله انتخاب مناسبترین ویژگی جهت تصمیم گیری اهمت فراوانی یافته است. روشهای کلاسیک انتخاب ویژگی نمی توانند بر روی داده های بزرگ به درستی عمل نمایند. از آنجا که مسئله انتخاب ویژگی یک مساله سخت و پیچیده  است، استفاده از الگوریتم‌های فرا ابتکاری جهت حل این مساله مناسب به نظر می‌رسد. در این مقاله الگوریتم فرا ابتکاری جدیدی با الهام از کوچ عشایر جهت حل مساله انتخاب ویژگی ارائه شده است. این الگوریتم به افتخار ایل قشقایی نامگذاری شده است. در این الگوریتم ترکیبی تابع تناسبی مبتنی بر الگوریتم انتخاب ویژگی و براساس کمینه‌سازی تعداد ویژگی‌ها و میزان خطای داده‌ها با استفاده از نتایج شبکه عصبی طراحی شد. سپس الگوریتم فرا ابتکاری قشقایی بر روی این تابع تناسب پیاده سازی شد و نتایج با الگوریتم های فرا ابتکاری مشهور ژنتیک و ازدحام ذرات مورد مقایسه قرار گرفت. نتایج آزمون فرض نشان داد که الگوریتم بهینه سازی قشقایی جهت حل مساله انتخاب ویژگی توسط الگوریتم ژنتیک و ازدحام ذرات مغلوب نمی‌گردد و به لحاظ همگرایی به جواب بهینه به خوبی آنها عمل می‌کند.

واژگان کلیدی: مساله انتخاب ویژگی، الگوریتم فرا ابتکاری، الگوریتم ژنتیک، الگوریتم ازدحام ذرات، الگوریتم قشقایی

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Introducing a new meta-heuristic algorithm to solve the feature selection problem

 

        

        Abstract

Due to the increase in the volume of data and information in recent years, the issue of choosing the most appropriate feature for decision making has become very important. Classic attribute selection methods cannot work well on big data. Because feature selection is a complex problem, it seems appropriate to use meta-heuristic algorithms to solve this problem. In this paper, a new meta-heuristic algorithm inspired by nomadic migration to solve the feature selection problem is presented. This algorithm is named in honor of the Qashqai tribe. In this hybrid algorithm, the proportional function was designed based on the feature selection algorithm and based on minimizing the number of features and the amount of data error using neural network results. Then the Qashqai meta-heuristic algorithm was implemented on this fitness function and the results were compared with the well-known meta-heuristic algorithms of genetics and particle swarm. The results of the hypothesis test showed that the Qashqai optimization algorithm to solve the feature selection problem by the genetic algorithm and particle swarm is not defeated and in terms of convergence to the optimal solution works well.

 

 

Keywords: Feature Selection Problem, Meta-heuristic Algorithm, Genetic Algorithm, Particle Swarm Algorithm, Qashqai Algorithm

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1-       مقدمه

در دهه‌های اخیر با پیشرفت سریع رایانه و افزایش حجم اطلاعات و داده با مفاهیمی مانند داده بزرگ و ابعاد زیاد مواجه شده‌ایم. افزایش ابعاد موجب افزایش هزینه محاسباتی سیستم شده و موجب کاهش دقت طبقه بندی می‌شود.[1] یک راهکار مهم جهت غلبه بر این مشکل استفاده از تکنیک های انتخاب ویژگی است که هدف آن انتخاب مناسبترین ویژگی‌ها از بین مجموعه ویژگیهای اولیه، برای افزایش عملکرد الگوریتمهای یادگیری است.  انتخاب ویژگی فرآیندی است که زیر مجموعه‌ای از ویژگی‌ها را براساس معیارهای بهینه سازی انتخاب می‌کند. انتخاب ویژگی در حل مسایل مختلفی از جمله مساله طبقه بندی[2] ، پیش‌بینی ورشکستگی بانک[3] ، دسته بندی متن[4]، خوشه بندی[5]، بخش بندی تصویر[6, 7] ، پزشکی [8, 9]، سیستم‌های قدرت[10]، تشخیص الگو[11]، پیش بینی بازار سهام[12]، تشخیص گفتار[7]، بازاریابی [13]، کاهش ابعاد [14]، تشخیص بدافزار تلفن همراه[15]  و تشخیص چهره[16] کاربرد دارد. روشهای مختلفی برای حل مساله انتخاب ویژگی ارائه شده است که از آن جمله می‌توان به روش فیلتر، پیچشی و ترکیبی اشاره نمود. در روش فیلتر با استفاده از معیارهای آماری برای هر ویژگی یک اعتبار محاسبه می‌شود. در روش پیچشی برای ارزیابی مجموعه ویژگیها از یک طبقه بندی استفاده می شود و مجموعه ویژگی که کمترین خطا و بهترین دقت را داشته باشد به عنوان بهترین مجموعه ویژگی انتخاب می‌گردد. روش‌های ترکیبی تلاش می‌کنند با ترکیب دو روش فیلتر و پیچشی از مزیت هر دو روش بهره ببرند. [17]

فرایند انتخاب ویژگی شامل سه مرحله روش جستجو، ارزیابی زیر مجوعه و معیار توقف می باشد.[2] مسئله انتخاب ويژگي، يکي از پيچيده‌ترين مسائل در بازشناسي الگو است و يک مسئله NP-Hard مي‌باشد و به همین دلیل برای حل مساله انتخاب ویژگی از روشهای فراابتکاری نیز استفاده شده است. مطالعات نشان داده است که در مجموعه‌های بزرگ، استفاده از روشهای فراابتکاری اثربخش تر از سایر روشها می باشد. با توجه به اینکه روشهای قطعی حل مساله انتخاب ویژگی علی الخصوص در انتخاب بهترین مجموعه ویژگی ها غالبا در بهینه محلی گرفتار شده و با توجه به پیچیده شدن مساله نیازمند زمان محاسباتی بالا بوده و غالبا در ارائه پاسخ صحیح ناکام بوده اند در سالهای اخیر محققان از الگوریتم های فرا ابتکاری جهت حل مساله انتخاب ویژگی استفاده نموده اند. با توجه به پیچیده شدن مسائل و در حال تغییر دنیای واقعی از سال 2000 به بعد شاهد ارائه الگوریتم های فرا ابتکاری جدید جهت حل مسائل مختلف هستیم. همچنین با توجه به نظریه ¹NFL که توسط ولپرت و مکریدی² در سال 1997 ارائه گردیده هیچ الگوریتم فرا ابتکاری نیست که جهت حل همه مسائل مناسب باشد. به همین علت ما در این مقاله با الهام گرفتن از نحوه همکاری های هوشمندانه کوچ عشایر الگوریتم فرا ابتکاری جدیدی را توسعه داده ایم. 

الگوریتمهای فراابتکاری الگوریتم‌هایی هستند که با الهام از فرایندهای طبیعی، فیزیکی، بیولوژیکی ارائه شده‌اند.  جهت حل مساله انتخاب ویژگی با استفاده از الگوریتم‌های فراابتکاری، هر جواب ممکن از مساله به صورت رشته‌ای از صفر و یک ها تعریف می‌شود. طول رشته مساوی تعداد کل ویژگیها بوده و مقدار صفر برای هر بیت نشان دهنده عدم انتخاب و مقدار یک بیانگر انتخاب ویژگی مربوطه می‌باشد. الگوریتمهای فرا ابتکاری از تابع شایستگی برای ارزیابی و جستجو استفاده نموده و به علت هوش جمعی، قادر به کشف جواب می‌باشند.[37] شکل شماره 1 فرایند کلی الگوریتم های فرا ابتکاری جهت دستیابی به پاسخ بهینه را نمایش می دهد.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

خیر

 

 

 

بلی

 

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

 

 

 

 

جدول 1 خلاصه‌ای از الگوریتم‌های فرا ابتکاری استفاده شده جهت حل مساله انتخاب ویژگی را نمایش می‌دهد.

ردیف	عنوان مقاله	نویسندگان	سال ارائه	مرجع
1	انتخاب مجموعه ویژگی با استفاده از الگوریتم ژنتیک	یانگ و هناوار	1998	[19]
2	انتخاب ویژگی با استفاده از روش جستجوی ممنوعه	ژانگ و سان	2002	[20]
3	انتخاب زیر مجموعه ویژگی مبتنی بر الگوریتم تکامل تفاضلی	خوشابا	2008	[21]
4	انتخاب مجموعه ویژگی با استفاده از الگوریتم هارمونی	دیائو و شن	2011	[22]
5	انتخاب ویژگی بر اساس رویکرد الگوریتم کرم شب تاب	باناتی و باجاج	2011	[23]
6	الگوریتم خفاش باینری جهت حل مساله انتخاب ویژگی	ناکامورا و پریرا	2012	[24]
7	یک الگوریتم انتخاب ویژگی جدید با استفاده از الگوریتم بهینه سازی ازدحام ذرات برای داده های سرطان	ساهو و میشرا	2012	[25]
8	انتخاب ویژگی داده ها بر اساس الگوریتم کلونی زنبور مصنوعی	شیزارو ، پدرینی	2013	[26]
9	الگوریتم فاخته باینری برای انتخاب ویژگی	رودریگز و یانگ	2013	[27]
10	انتخاب مجموعه ویژگی با استفاده از الگوریتم رقابت استعماری اصلاح شده	موسوی راد و ابراهیم پور	2013	[28]
11	یک روش بسته بندی برای انتخاب ویژگی های مبتنی بر الگوریتم خفاش	رودریگز ، پیرا و ماکامورا	2014	[29]
12	انتخاب زیر مجموعه ویژگیها با استفاده از الگوریتم جستجوی گرانشی باینری بهبود یافته	ارشادی و نظام آبادی پور	2014	[30]
13	یک الگوریتم مورچه پیشرفته برای انتخاب زیر مجموعه ویژگی ها	کاشف  و نظام آبادی پور	2015	[31]
14	انتخاب زیر مجموعه ویژگی با رویکرد بهینه سازی گرگ خاکستری	اماری، زاوبا و گروسان	2015	[32]
15	انتخاب ویژگی با استفاده از الگوریتم جمعیت مورچگان	نظام آبادی پور	2015	[18]
16	انتخاب ویژگی ها با استفاده از الگوریتم بهینه سازی جنگل	قائمی، فیضی درخشی	2016	[33]
17	الگوریتم بهینه سازی نهنگ برای انتخاب ویژگی	مفرجا و میرجلیلی	2018	[34]
18	انتخاب ویژگی ها و الگوریتم دسته میگو پیشرفته برای خوشه بندی اسناد متنی	ابولیگا	2019	[35]

 

·       مساله تحقیق:

1-       ارائه یک الگوریتم فرا ابتکاری جدید باعملکرد بهتر نسبت به سایر الگوریتمها در یافتن جواب بهینه در برخی مسائل با الهام از نحوه کوچ ایل عشایر قشقایی و آزمون آن با بهره گیری از 11 تابع نمونه استاندارد معروف بهینه سازی و انجام آزمون فرض آماری مقایسه میانگین پاسخ با الگوریتم ژنتیک³، ازدحام ذرات⁴ 

2-       حل مساله انتخاب ویژگی جهت انتخاب ویژگی های مناسب در داده های حجم بالا با الگوریتم فرا ابتکاری عشایر قشقایی با استفاده از پنج مجموعه داده (دیتاست) معروف نرم افزار متلب چربی بدن⁵ ، قیمت گذاری خانه⁶، حلقه های پوسته صدف⁷، انرژی ساختمان⁸  و مجموعه داده شیمی⁹ مقایسه نتایج با الگوریتم ژنتیک و الگوریتم ازدحام ذرات

 

·       متدولوژی و روش شناسی تحقیق:

1-       بررسی ادبیات موضوع مساله انتخاب ویژگی

2-       بررسی الگوریتمهای فرا ابتکاری ارائه شده جهت حل مساله انتخاب ویژگی

3-       طراحی الگوریتمهای فرا ابتکاری جدید با با الهام از نحوه کوچ ایل عشایر قشقایی

4-       آزمون مقایسه نتایج الگوریتم فرا ابتکاری عشایر قشقایی با بهره گیری از 11 تابع نمونه استاندارد معروف بهینه سازی و انجام آزمون فرض آماری مقایسه میانگین پاسخ با الگوریتم ژنتیک، ازدحام ذرات . بررسی های آماری و مقایسه میانگین تابع هدف از نرم افزار SPSS و برای تنظیم پارامترها از روش تاگوچی از نرم فزار (Minitab) صورت پذیرفت.

5-       حل مساله انتخاب ویژگی جهت انتخاب ویژگی های مناسب در داده های حجم بالا با الگوریتم فرا ابتکاری عشایر قشقایی با استفاده از پنج مجموعه داده (دیتاست) معروف نرم افزار متلب¹⁰ ، شامل دیتاست چربی بدن¹¹ ، قیمت گذاری خانه¹²، حلقه های پوسته صدف¹³، انرژی ساختمان¹⁴  و مجموعه داده شیمی¹⁵ مقایسه نتایج با الگوریتم ژنتیک و الگوریتم ازدحام ذرات

جدول  شماره یک توابع نمونه استاندارد به همراه مشخصات آنها را نمایش می دهد.

                

جدول 1-  توابع نمونه استاندارد به همراه مشخصات آنها

 

2-       الگوریتم فرا ابتکاری عشایر قشقایی( (QA

یک الگوریتم بهینه‌سازی فرا‌ ابتکاری، یک روش سطح بالاتر ابتکاری است که می‌تواند به ویژه با اطلاعات اندک و با تغییر‌هایی کم جهت جستجو کردن و یافتن راه حل بهینه برای مسائل مختلف بهینه‌سازی به کار رود. استفاده از الگوریتم‌های فرا‌ ابتکاری، به طور قابل ملاحظه‌ای توانایی یافتن جواب‌های با کیفیت بالا را برای حل مسائل بهینه سازی سخت افزایش می‌دهد. ویژگی مشترک این الگوریتم‌ها، استفاده از مکانیزم‌های خروج از بهینه محلی است.[36]

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

 

شکل 2- کوچ عشایرقشقایی

3-       روش طراحی الگوریتم فرا ابتکاری عشایر قشقایی

3-1 ایجاد جمعیت اولیه

فرض کنیم ایل n تا عضو دارد، هرکدام یک نقطه شروع کوچ (از ییلاق به قشلاق و بالعکس) دارند. نقطه شروع کوچ هر کدام از اعضای ایل یک نقطه تصادفی در فضای شدنی مسئله می‌باشد.

3-2 انتخاب نخبه¹⁶ 

معمولاً ایلات دارای سرزمین و قلمرو ایلی خاص خود بوده و تحت رهبری و مدیریت شخصی با سمت ایلخان یا ایل بیگ اداره می‌شوند. بزرگان ایل و ریش سفیدان مجموعه‌ای غنی از تجارب در خصوص بهترین و کم خطر‌ترین مسیرهای عبور در حافظه خود دارند و در عبور از مسیرهای کوچ بیشتر به حافظه بلندمدت خود مراجعه می‌کنند. این در حالی است که اعضای جوان‌تر ایل از تجربه و حافظه کوتاه مدت تری برخوردار بوده و به همین دلیل کمتر به حافظه خود مراجعه می‌کنند و بیشتر به موقعیت قبلی خود استناد می‌کنند. در نقطه مقابل افراد ریش سفید ایل کمتر به موقعیت قبلی خود را ملاک حرکت بعدی خود قرار می‎دهند. از این مورد جهت به روز رسانی مکان‌های جدید حرکت الگوریتم الهام گرفته شده است.

3-3 نحوه به روز رسانی مکان‌های جدید

در این الگوریتم عضو دارای بهترین تابع هزینه به عنوان ایلخان انتخاب و جهت به روز رسانی محل جدید آن از رابطه (1) استفاده شده است.

     

    رابطه (1)

 

دیگر اعضای جمعیت طبق رابطه (2) به روز رسانی شده است.  بهترین راه حل در هر تکرار و بدترین راه حل می‌باشند. 

 

رابطه (2)

·       پارامترهای الگوریتم قشقایی به شرح زیر می باشد:

نام تابع	فرمول تابع	دامنه تابع	نقطه بهینه (کمینه تابع)	مقدار تابع در نقطه کمینه
F1 Sphere
F2 Rastrigin
F3 Rosenbrock
F4 Griewank
F5 Ackley
F6 EggHolder
F7 Michalewicz
F8 Six-Hump Camel
F9 Levy
F10 Rotated Hyper-Ellipsoid
F11 Shubert			18 global minima

3-4 مسیر کوچ

مجموعه‌ای از بهترین نقاط طی شده (بهترین جواب‌ها) مسیر کلی حرکت کوچ را تشکیل می‌دهد.

3-5 استراتژی پیشگیری از بدتر شدن جواب بهینه

در این الگوریتم یک استراتژی جهت جلوگیری از بدتر شدن جواب بهینه اتخاذ گردید، به این نحو که اگر جواب بهینه الگوریتم در یک تکرار از تکرار قبلی الگوریتم بدتر شد، بدترین جواب تکرار فعلی با نقطه بهینه تکرار قبلی جایگزین می‌گردد و بدین نحو از بدتر شدن جواب جلوگیری خواهد شد.

 

3-6 استراتژی تنوع و تمرکز

استراتژی تنوع و تمرکز در این الگوریتم به این نحو می‌باشد که هرچه توجه به موقعیت قبلی بیشتر باشد تمرکز¹⁷ بیشتری خواهیم داشت و هر چه توجه به موقعیت قبلی کمتر باشد تنوع¹⁸ بیشتری را شاهد خواهیم بود.

3-7 شرایط توقف الگوریتم

شرایط متفاوتی را می‌توان برای توقف الگوریتم مانند مدت زمان اجرای مشخص، تعداد تکرار مشخص، عدم بهبود جواب در نظر گرفت.

 

3-8 شبه‌کد الگوریتم قشقایی

جدول1 شبه‌کد¹⁹ الگوریتم قشقایی را نمایش می‌دهد.

جدول 2- شبه‌کد الگوریتم بهینه‌سازی قشقایی(QA)

: حداکثر تعداد اعضای ایل	Varmax
: موقعیت عضو iام ایل در تکرار t
: موقعیت عضو iام ایل در تکرار t+1
: عضو i ام جمعیت ایل	Pop(i)
: تابع تناسب عضو i جمعیت ایل
: حداقل تعداد اعضای ایل	Varmin
: پارامترهای الگوریتم	C1, C2
: بهترین راه حل (پاسخ) هر تکرار
: بدترین راه حل(پاسخ) هر تکرار

Result: Find The best solution         Objective min or max Generate initial population, of n members of tribes(or nomads) Find the best solution  in the population in each iteration While(t<MaxIteration) or (stop criterion) do For i=1:n (all n members of each tribe’s)               Best solution(it)               Worst solution(it) Update Position if pop(i) is best solution of each Iteration then else   end if Evaluate new solutions If new solutions are better, update them in the population end for Find the current best solution end while   4-       تنظیم پارامترها با توجه به اینکه خروجی الگوریتم های فرا ابتکاری تحت تاثیر پارامترهای ورودی آنها می باشد، به منظور تنظیم پارامترها از روش تاگوچی و نرم افزار Minitab  استفاده شده است. بر اساس جدول شماره 3 در پنج سطح برای پارامترهای MaxIt، Npop ، C1  و C2 تنظیم پارامتر الگوریتم فرا ابتکاری عشایر قشقایی انجام شده است. جدول 3- تنظیم پارامترهای الگوریتم عشایر قشقایی ردیف پارامتر سطح اول سطح دوم سطح سوم سطح چهارم سطح پنجم 1 MaxIt 50 100 150 200 250 2 Npop 50 100 150 200 250 3 C1 0.1 0.5 1 2 3 4 C2 0.1 0.5 1 2 3 شکل 3 و 4 تحلیل نتایج حاصل از اجرای تنظیم پارامترها روش تاگوچی با استفاده از نرم افزار Minitab  را نمایش می دهد که با توجه به آن  MaxIt=200 ، 250= Npop،0.5 = C1و 3= C2 بهترین عملکرد را ارائه داده اند.   شکل 3- نمودار میانگین میانگین ها برای هر سطح از پارامترهای الگوریتم عشایر قشقایی       شکل 4- نمودار میانگین   S/N برای هر سطح از پارامترهای الگوریتم عشایر قشقایی           5-       ارائه الگوریتم ترکیبی انتخاب ویژگی و الگوریتم قشقایی( (QA شکل 5 گام های روش ارائه شده در این مقاله را نشان می دهد.   شکل 5- مراحل طراحی و پیاده سازی الگوریتم پیشنهادی جهت حل مساله انتخاب ویژگی 6-       نتایج محاسباتی جهت انجام آزمایش ها از مجموعه داده تصادفی مطابق با مشخصات جدول4 استفاده شد.  این مجموعه داده ها از مجموعه داده نرم افزار متلب سایت ( https://www.mathworks.com/) استفاده شده است.  جدول 4- مشخصات مجموعه داده های مورد آزمون مجموعه داده تعداد ویژگی تعداد نمونه Body fat 13 252 House pricing 13 506 Abalone Rings                 8 4177 Building Energy 14 4208 Chemical 8 498   برای ارزیابی الگوریتم پیشنهادی، الگوریتم ژنتیک و الگوریتم ازدحام ذرات بر روی مساله انتخاب ویژگی با مجموعه داده های مندرج در جدول 2 پیاده سازی شده است. الگوریتم قشقایی بر روی مساله انتخاب ویژگی پیاده سازی و با استفاده از مجموعه داده های جدول 2، 30 بار متوالی اجرا شد و نتایج حاصل با الگوریتم های فرا ابتکاری مشهور ژنتیک و ازدحام ذرات با توجه به فرضیات مندرج در جدول 3 مورد مقایسه قرار گرفت.  جدول 5- آزمون فرضیات انجام شده به دلیل اینکه مقایسات دو نمونه مستقل می‌باشد از آزمون من ویتنی20 استفاده شد. الگوریتم‌های ژنتیک و ازدحام ذرات جهت مقایسه نتایج تابع هزینه الگوریتم پیشنهادی مورداستفاده قرار گرفت. برای انجام محاسبات از یک رایانه با مشخصات جدول 4 مورد استفاده قرارگرفت.  جدول 6- مشخصات رایانه مورد استفاده جهت مقایسه نتایج   در جدول 7و8 نتایج اجرای الگوریتم قشقایی در مقایسه با الگوریتم ژنتیک و ازدحام ذرات نمایش داده شده است. جدول 7- مقایسه میانگین نتایج حاصل از 30 بار اجرای الگوریتم قشقایی و الگوریتم ژنتیک بر روی توابع آزمون(تابع هزینه) آزمون فرضیات حل مساله انتخاب ویژگی با الگوریتم فرا ابتکاری قشقایی(تابع محک) : الگوریتم ژنتیک بر الگوریتم پیشنهادی(عشایر قشقایی) غلبه می‌کند.   : الگوریتم ژنتیک بر الگوریتم پیشنهادی(عشایر قشقایی) غلبه نمی‌کند.   : الگوریتم ازدحام ذرات بر الگوریتم پیشنهادی(عشایر قشقایی) غلبه می‌کند.   : الگوریتم ازدحام ذرات بر الگوریتم پیشنهادی(عشایر قشقایی) غلبه نمی‌کند.   آزمون فرضیات حل مساله انتخاب ویژگی با الگوریتم فرا ابتکاری قشقایی  : الگوریتم ژنتیک بر الگوریتم قشقایی در حل مساله انتخاب ویژگی غلبه می‌کند.   : الگوریتم ژنتیک بر الگوریتم قشقایی در حل مساله انتخاب ویژگی غلبه نمی‌کند.   : الگوریتم ازدحام ذرات بر الگوریتم قشقایی در حل مساله انتخاب ویژگی غلبه می‌کند.   : الگوریتم ازدحام ذرات بر الگوریتم قشقایی در حل مساله انتخاب ویژگی غلبه نمی‌کند.     جدول 8 - مقایسه میانگین نتایج حاصل از 30 بار اجرای الگوریتم قشقایی و الگوریتم ژنتیک بر روی توابع آزمون(زمان محاسباتی) ردیف توابع آزمون میانگین تابع هزینه P-Value حد پذیرش خطا نتیجه آزمون فرض QA GA 1 Sphere 2.01E-290 1.90E-02 0 α=0.05  رد می‌شود 2 Rastrigin 0 1.94E+00 0 α=0.05  رد می‌شود 3 Rosenbrock 3.98E+00 7.13E+00 0.008 α=0.05  رد می‌شود 4 Griewank 0 4.53E-02 0 α=0.05  رد می‌شود 5 Ackley 8.88E-16 2.58E-01 0 α=0.05  رد می‌شود 6 EggHolder -8.24E+02 -7.38E+02 0.156 α=0.05  رد نمی‌شود 7 Michalewicz -1.51E+00 -1.75E+00 0 α=0.05  رد می‌شود 8 Six-Hump Camel 4.77E-01 7.57E-03 0 α=0.05  رد می‌شود 9 Levy 3.89E-01 1.07E-01 0 α=0.05  رد می‌شود 10 Rotated Hyper-Ellipsoid 4.65E-55 1.44E+00 0 α=0.05  رد می‌شود 11 Shubert -1.37 E+02 -1.79E+02 0 α=0.05  رد می‌شود خلاصه نتایج حاصل از جدول 7 و 8 در جدول 9 آورده شده است: جدول 9- جمع بندی مقایسه نتایج حاصل از اجرای الگوریتم قشقایی و الگوریتم ژنتیک بر روی 11 تابع آزمون ردیف توابع آزمون میانگین زمان محاسباتی P-Value حد پذیرش خطا نتیجه آزمون فرض QA GA 1 Sphere 2.87E-01 1.86E+00 0 α=0.05  رد می‌شود 2 Rastrigin 2.74E-01 1.83E+00 0 α=0.05  رد می‌شود 3 Rosenbrock 2.76E-01 1.68E+00 0 α=0.05  رد می‌شود 4 Griewank 2.77E-01 1.70E+00 0 α=0.05  رد می‌شود 5 Ackley 2.80E-01 1.72E+00 0 α=0.05  رد می‌شود 6 EggHolder 2.70E-01 2.50E+00 0 α=0.05  رد می‌شود 7 Michalewicz 2.33E-01 1.78E+00 0 α=0.05  رد می‌شود 8 Six-Hump Camel 2.89E-01 1.62E+00 0 α=0.05  رد می‌شود 9 Levy 3.37E-01 1.57E+00 0 α=0.05  رد می‌شود 10 Rotated Hyper-Ellipsoid 2.86E-01 1.60E+00 0 α=0.05  رد می‌شود 11 Shubert 2.48E-01 1.58E+00 0 α=0.05  رد می‌شود به این ترتیب می‌توان نتیجه گیری کرد که الگوریتم ژنتیک بر الگوریتم قشقایی نسبت به الگوریتم ژنتیک هم از لحاظ همگرایی به راه حل بهینه و هم به لحاظ زمان محاسباتی غلبه نمی‌کند. به این ترتیب می‌توان نتیجه گیری کرد که الگوریتم ژنتیک بر الگوریتم قشقایی نسبت به الگوریتم ژنتیک هم از لحاظ همگرایی به راه حل بهینه و هم به لحاظ زمان محاسباتی غلبه نمی‌کند. جدول10- مقایسه میانگین نتایج حاصل از 30 بار اجرای الگوریتم قشقایی و الگوریتم‌ ازدحام ذرات بر روی توابع آزمون(تابع هزینه) نتیجه آزمون فرض تابع هزینه زمان محاسباتی  رد می شود  رد نمی شود  رد می شود  رد نمی شود آزمون فرض غلبه الگوریتم ژنتیک  بر الگوریتم قشقایی (QA) تعداد 10 1 11 0 لازم به توضیح است که nPop=10 و100MaxIt= و 5= nVarدرنظر گرفته شده است. جدول 11- مقایسه میانگین نتایج حاصل از 30 بار اجرای الگوریتم قشقایی و الگوریتم ازدحام ذرات بر روی توابع آزمون(زمان محاسباتی) ردیف توابع میانگین تابع هزینه Sig حد پذیرش خطا نتیجه آزمون فرض QA PSO 1 Sphere 2.01E-290 2.34E-07 0 α=0.05   2 Rastrigin 0 4.41E+00 0 α=0.05   3 Rosenbrock 3.98E+00 2.00E+00 0 α=0.05   4 Griewank 0 2.27E-02 0 α=0.05   5 Ackley 8.88E-16 5.71E-02 0 α=0.05   6 EggHolder -8.24E+02 -5.56E+02 0 α=0.05   7 Michalewicz -1.51E+00 -1.80E+00 0 α=0.05   8 Six-Hump Camel 4.77E-01 4.69E-08 0 α=0.05   9 Levy 3.89E-01 1.88E-01 0 α=0.05   10 Rotated Hyper-Ellipsoid 4.65E-55 2.68E-06 0 α=0.05   11 Shubert -1.37E+02 -1.87E+02 0 α=0.05   خلاصه نتایج حاصل از جداول 10 و 11 ، در جدول 12 نمایش داده شده است. جدول 12- مقایسه نتایج حاصل از اجرای الگوریتم قشقایی و الگوریتم ازدحام ذرات بر روی 11 تابع آزمون ردیف توابع میانگین زمان محاسباتی Sig حد پذیرش خطا نتیجه آزمون فرض QA PSO 1 Sphere 2.87E-01 2.56E-01 0 α=0.05   2 Rastrigin 2.74E-01 2.99E-01 0.081 α=0.05  رد نمی‌شود 3 Rosenbrock 2.76E-01 2.57E-01 0 α=0.05   4 Griewank 2.77E-01 2.53E-01 0 α=0.05   5 Ackley 2.80E-01 2.51E-01 0 α=0.05   6 EggHolder 2.70E-01 2.46E-01 0 α=0.05   7 Michalewicz 2.33E-01 2.51E-01 0 α=0.05   8 Six-Hump Camel 2.89E-01 2.41E-01 0 α=0.05   9 Levy 3.37E-01 2.54E-01 0 α=0.05   10 Rotated Hyper-Ellipsoid 2.86E-01 2.48E-01 0 α=0.05   11 Shubert 2.48E-01 2.28E-02 0.69 α=0.05  رد نمی‌شود بر اساس اطلاعات جدول 12 می‌توان نتیجه گیری کرد که الگوریتم ازدحام ذرات بر الگوریتم قشقایی هم از لحاظ همگرایی به راه حل بهینه و هم به لحاظ زمان محاسباتی برتری ندارد. جدول 13 میانگین نتایج حاصل از 30 بار اجرای الگوریتم ژنتیک و الگوریتم قشقایی بر روی مساله انتخاب ویژگی را نمایش می‌دهد. جدول 13- مقایسه میانگین نتایج حاصل از 30 بار اجرای الگوریتم قشقایی و الگوریتم ژنتیک بر روی مساله انتخاب ویژگی نتیجه آزمون فرض تابع هزینه زمان محاسباتی  رد می شود  رد نمی شود  رد می شود  رد نمی شود آزمون فرض غلبه الگوریتم ازدحام ذرات  بر الگوریتم قشقایی (QA) تعداد 11 0 9 2 جدول14 میانگین نتایج حاصل از 30 بار اجرای الگوریتم قشقایی و الگوریتم ازدحام ذرات بر روی مساله انتخاب ویژگی را نمایش می دهد. جدول 14- مقایسه میانگین نتایج حاصل از 30 بار اجرای الگوریتم قشقایی و الگوریتم ازدحام ذرات بر روی مساله انتخاب ویژگی ردیف مجموعه داده میانگین تابع تناسب P-Value حد پذیرش خطا نتیجه آزمون فرض QA GA 1 Body fat dataset 2.08E+01 1.96E+01 0 α=0.05  رد می‌شود 2 House pricing dataset 1.04E+01 1.05E+01 0 α=0.05  رد می‌شود 3 Abalone Rings dataset 5.40E+00 5.59E+00 0 α=0.05  رد می‌شود 4 Building Energy dataset 3.27E-03 3.39E-03 0 α=0.05  رد می‌شود 5 Chemical dataset 3.37E+00 4.35E+00 0 α=0.05  رد می‌شود به این ترتیب با توجه به نتایج جداول13 و 14 می‌توان نتیجه گیری کرد که الگوریتم‌های ژنتیک و ازدحام ذرات در زمینه حل مساله انتخاب ویژگی از لحاظ همگرایی به راه حل بهینه ارائه شده توسط الگوریتم قشقایی غلبه نمی‌کنند.   7-       جمع بندی و نتیجه گیری انتخاب ویژگی یکی از روشهای پرکاربرد در مبحث یادگیری ماشینی است که در حل مسائل مختلف علمی از قبیل پزشکی، زیست‌‌‌شناسی، تشخیص بیماری، بخش بندی بازار، انتخاب تامین کنندگان، پردازش تصویر و هوش مصنوعی مورد توجه پژوهشگران قرار گرفته است.  در این مقاله یک الگوریتم فرا ابتکاری جدید جهت حل مساله انتخاب ویژگی به نام الگوریتم قشقایی ارائه گردید. الگوریتم قشقایی با الهام از نحوه کوچ عشایر طراحی شده است. در این الگوریتم ترکیبی تابع تناسبی مبتنی بر الگوریتم انتخاب ویژگی  و براساس کمینه‌سازی تعداد ویژگی‌ها و میزان خطای داده‌ها با استفاده از نتایج شبکه عصبی طراحی شد. سپس الگوریتم فرا ابتکاری قشقایی بر روی این تابع تناسب پیاده سازی شد و نتایج با الگوریتم های فرا ابتکاری مشهور ژنتیک و ازدحام ذرات مورد مقایسه قرار گرفت. نتایج آزمون فرض نشان داد که الگوریتم بهینه سازی قشقایی جهت حل مساله انتخاب ویژگی توسط الگوریتم ژنتیک و ازدحام ذرات مغلوب نمی‌گردد و به لحاظ همگرایی به جواب بهینه به خوبی آنها عمل می‌کند. جهت پژوهش های آتی توصیه می گردد الگوریتم ارائه شده جهت حل سایر مسائل از جمله خوشه بندی نیز مورد استفاده قرار گیرد.     منابع: .1        Kabir, M.M., M. Shahjahan, and K. Murase, A new hybrid ant colony optimization algorithm for feature selection. Expert Systems with Applications, 2012. 39(3): p. 3747-3763. .2        Dash, M. and H. Liu, Feature selection for classification. Intelligent data analysis, 1997. 1(3): p. 131-156. .3        Tsai, C.-F., Feature selection in bankruptcy prediction. Knowledge-Based Systems, 2009. 22(2): p. 120-127. .4        Dasgupta, A., et al. Feature selection methods for text classification. in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. 2007. .5        Roth, V. and T. Lange. Feature selection in clustering problems. in Advances in neural information processing systems. 2004. .6        Huang, K. and S. Aviyente, Wavelet feature selection for image classification. IEEE Transactions on Image Processing, 2008. 17(9): p. 1709-1720. .7        Rong, J., G. Li, and Y.-P.P. Chen, Acoustic feature selection for automatic emotion recognition from speech. Information processing & management, 2009. 45(3): p. 315-328. .8        Llamedo, M. and J.P. Martínez, Heartbeat classification using feature selection driven by database generalization criteria. IEEE Transactions on Biomedical Engineering, 2011. 58(3): p. 616-625. .9        Lavanya, D. and D.K.U. Rani, Analysis of feature selection with classification: Breast cancer datasets. Indian Journal of Computer Science and Engineering (IJCSE), 2011. 2(5): p. 756-763. .10        Jensen, C.A., M.A. El-Sharkawi, and R.J. Marks, Power system security assessment using neural networks: feature selection using Fisher discrimination. IEEE Transactions on power systems, 2001. 16(4): p. 757-763. .11        Kittler, J., Mathematical methods of feature selection in pattern recognition. International Journal of Man-Machine Studies, 1975. 7(5): p. 609-638. .12        Huang, C.-L. and C.-Y. Tsai, A hybrid SOFM-SVR with a filter-based feature selection for stock market forecasting. Expert Systems with Applications, 2009. 36(2): p. 1529-1539. .13        Meiri, R. and J. Zahavi, Using simulated annealing to optimize the feature selection problem in marketing applications. European Journal of Operational Research, 2006. 171(3): p. 842-858. .14        Mladenić, D. Feature selection for dimensionality reduction. in International Statistical and Optimization Perspectives Workshop" Subspace, Latent Structure and Feature Selection". 2005. Springer. .15        Feizollah, A., et al., A review on feature selection in mobile malware detection. Digital investigation, 2015. 13: p. 22-37. .16        Kanan, H.R., K. Faez, and M. Hosseinzadeh. Face recognition system using ant colony optimization-based selected features. in 2007 IEEE Symposium on Computational Intelligence in Security and Defense Applications. 2007. IEEE. .17        Hsu, H.-H., C.-W. Hsieh, and M.-D. Lu, Hybrid feature selection by combining filters and wrappers. Expert Systems with Applications, 2011. 38(7): p. 8144-8150. .18        Kashef, S., & Nezamabadi-pour, H. (2015). An advanced ACO algorithm for feature subset selection. Neurocomputing, 147, 271-279. .19        Yang, J. and V. Honavar, Feature subset selection using a genetic algorithm, in Feature extraction, construction and selection. 1998, Springer. p. 117-136. .20        Zhang, H. and G. Sun, Feature selection using tabu search method. Pattern recognition, 2002. 35(3): p. 701-711. .21        Khushaba, R.N., A. Al-Ani, and A. Al-Jumaily. Differential evolution based feature subset selection. in 2008 19th International Conference on Pattern Recognition. 2008. IEEE. .22        Diao, R. and Q. Shen, Feature selection with harmony search. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2012. 42(6): p. 1509-1523. .23        Banati, H. and M. Bajaj, Fire fly based feature selection approach. International Journal of Computer Science Issues (IJCSI), 2011. 8(4): p. 473. .24        Nakamura, R.Y., et al. BBA: a binary bat algorithm for feature selection. in 2012 25th SIBGRAPI conference on graphics, Patterns and Images. 2012. IEEE. .25        Sahu, B. and D. Mishra, A novel feature selection algorithm using particle swarm optimization for cancer microarray data. Procedia Engineering, 2012. 38: p. 27-31. .26        Schiezaro, M. and H. Pedrini, Data feature selection based on Artificial Bee Colony algorithm. EURASIP Journal on Image and Video Processing, 2013. 2013(1): p. 47. .27        Rodrigues, D., et al. BCS: A binary cuckoo search algorithm for feature selection. in 2013 IEEE International Symposium on Circuits and Systems (ISCAS). 2013. IEEE. .28        Mousavirad, S. and H. Ebrahimpour-Komleh. Feature selection using modified imperialist competitive algorithm. in ICCKE 2013. 2013. IEEE. .29        Rodrigues, D., et al., A wrapper approach for feature selection based on bat algorithm and optimum-path forest. Expert Systems with Applications, 2014. 41(5): p. 2250-2258. .30        Rashedi, E. and H. Nezamabadi-pour, Feature subset selection using improved binary gravitational search algorithm. Journal of Intelligent & Fuzzy Systems, 2014. 26(3): p. 1211-1221. .31        Kashef, S. and H. Nezamabadi-pour, An advanced ACO algorithm for feature subset selection. Neurocomputing, 2015. 147: p. 271-279. .32        Emary, E., et al. Feature subset selection approach by gray-wolf optimization. in Afro-European conference for industrial advancement. 2015. Springer. .33        Ghaemi, M. and M.-R. Feizi-Derakhshi, Feature selection using forest optimization algorithm. Pattern Recognition, 2016. 60: p. 121-129. .34        Mafarja, M. and S. Mirjalili, Whale optimization approaches for wrapper feature selection. Applied Soft Computing, 2018. 62: p. 441-453. .35        Abualigah, L.M.Q., Feature selection and enhanced krill herd algorithm for text document clustering. 2019: Springer. .36        Yang, X.-S., Engineering optimization: an introduction with metaheuristic applications. 2010: John Wiley & Sons. 37.          Khadem, M., Toloie Eshlaghy, A., & Fathi Hafshejani, K. (2021). Nature-inspired metaheuristic algorithms: literature review and presenting a novel classification. Journal of Applied Research on Industrial Engineering. https://doi.org/10.22105/jarie.2021.287733.1330                       1           [1]  No Free Lunch [2]  Wolpert and Macready [3]  Genetic Algorithm(GA) [4] Particle Swarm Optimization(PSO)   [5]  Body fat dataset [6]  House pricing dataset [7]  Abalone shell rings dataset [8]  Building energy dataset [9]  Chemical dataset [10]  Matlab Software [11]  Body fat dataset) https://www.mathworks.com/( [12] House pricing dataset) https://www.mathworks.com/( [13]  Abalone shell rings dataset) https://www.mathworks.com/( [14]  Building energy dataset) https://www.mathworks.com/( [15]  Chemical dataset) https://www.mathworks.com/( [16] Elite Selection          [17]  Centralization,Concenteration,Intensification [18]  Diversification [19]  Pseudo Code [20]  Mann-WhitneyTest