یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
الگوریتم جستجوی ممنوعه برای انتخاب ویژگی

در مقالات مرتبط با اتخاب ویژگی با استفاده از الگوریتم جستجوی ممنوعه،Zhang  و Sun[Zhan02]و همچنین Tahir[Tahi07]، هر دوی ان­ها از حافظه کوتاه مدت (Tabu List)در الگوریتم­های خود استفاده کرده­اند و [Tahi05]از حافظه میان مدت[1] استفاده کرده است.

یک اشکال الگوریتم TSبا حافظه کوتاه مدت یا میان مدت، این است که اندازه TLباید با لطافت خاصی تنظیم شود که این کار عمومیت ندارد. اگر هم این کار انجام شود، یک لیست ممنوعه با سایز متناهی Lهنوز نمی­تواند ضمانت کند که فرایند جستجو در چرخه جواب با اندازه بزرگتر از Lنیفتد. نتایج نظری موجود برای تشخیص اندازه Lهنوز ناکارامد است [Dréo06].

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

جواب­های کاندید شامل دو قسمت می­شوند:

1)    تمام جواب­های کاندید در تکرار قبلی، بجز ان­هایی که در لیست ممنوعه قرار دارند.

2)    تمام همسایه­های مستقیم جواب جاری بجز ان­هایی که در لیست ممنوعه قرار دارند.

تفاوت دیگر این الگوریتم با دو الگوریتم قبلی، این است که نیازی به معیار تنفس ندارد.

با در نظر گرفتن موارد و نمادهای زیر، به شرح الگوریتم می­پردازیم [Yong09]:

             عملگر تفاضل نظری مجموعه­ها

F            مجموعه ویژگی اصلی با nویژگی، |F|=n

S            مجموعه جواب ویژگی با mویژگی برای تکرار جاری، |S|=m ≤ n

N(S)+      همسایه­های مستقیم Sبا یک ویژگی جدید مشمول شده در S

N(S)-       همسایه­های مستقیم Sبا یک ویژگی موجود مستثنی شده از S

N(S)        تمام همسایه­های مستقیم S، N(S) = N(S)+  N(S)-

TL          لیست ممنوعه، تمام جواب­هایی که ممنوع هستند.

CL         لیست کاندید، تمام جواب­های کاندید برای تکرار بعدی

Sk          kامین جواب کاندید در CL

J(Sk)       مقدار تابع ارزیاب برای Sk

i             شمارنده تکرار

الگوریتم جستجوی ممنوعه با حافظه بلند مدت، به شرح زیر می­باشد:

a)   مقدار­دهی اولیه[2] : قرار بده ,CL =   i=1 ,TL = و Sرا با یک مجموعه شدنی و ممکن اغاز کن.

b)  تولید لیست ممنوعه : قرار بده CL = (CL  N(S)) TL.

c)   ارزیابی : توسط تابع ارزیاب مقدار هر جواب کاندید J(Sk)را به دست اور که Sk  CL.

d)   بهترین جواب را برای تکرار بعدی پیدا کن، S = argmaxSkCLJ(Sk).

e)   Sرا در لیست ممنوعه قرار بده و از لیست کاندید حذف کن، ,TL = TL  SCL=CLS .

f)      شمارنده تکرار را بروز کن، i = i+1.

g)     مراحل bتا fرا تکرار کن تا به یکی از شرط­های زیر برخورد کنی:

1)    به یک شماره تکرار که از قبل تعیین شده، رسیده شود.

2)    لیست کاندید CLتهی شود.

بهترین جواب پیدا شده تاکنون را بازگردان



[1] intermediate-term memory

[2] Initialization

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26