لیست الگوریتم فرا ابتکاری

الگوریتم فراابتکاری یا متاهیوریستیک (به انگلیسی Meta Heuristic) که به آنها الگوریتم های فراتکاملی هم گاها گفته میشود، دسته ای از الگوریتم هایی هستند که برای حل مسائل بهینه سازی به کار برده میشوند.

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

• الگوریتم های دقیق یا exact
• الگوریتم های تقریبی یا approximate

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

الگوریتم های تقریبی یا approximate میتوانند در زمان کوتاه و قابل قبولی ، پاسخ های خوب (نزدیک به بهینه) را برای مسائل سخت و پیچیده پیدا کنند ، و از این نظر بسیار کاربردی و مهم هستند.

الگوریتم های تقریبی را میتوان در سه دسته تقسیم کرد:

1. الگوریتم های ابتکاری heuristic
2. الگوریتم های فراابتکاری Meta heuristic
3. الگوریتم های ابرابتکاری یا Hyper heuristic

الگوریتم های ابتکاری یا heuristic در واقع الگوریتم های اولیه ای بودند که با بکاربردن تابع اکتشاف ، گامی برای حل مسائل مختلف در هوش مصنوعی برداشتند. الگوریتم هایی مانند جستجوی عمقی ، جستجوی عرضی ، A* و غیره.

اما مشکلاتی مانند گیرافتادن در بهینه محلی و همگرایی زودرس که در اغلب الگوریتم های ابتکاری وجود دارد، منجر به پیدایش الگوریتم های فراابتکاری یا meta heuristic شد.

الگوریتم های فراابتکاری ، با بهره گیری از دو مکانیزم مهم و کلیدی بنام اکتشاف (Exploration) و بهره برداری (Exploitation) توانایی فرا از بهینه محلی و رسیدن به بهینه سراسری را دارند.

تفاوت association با Community

تفاوت اصلی بین مفهوم "association" و "community" در ارتباط با شبکه‌ها یا گراف‌ها به شرح زیر است:

Associationیا ارتباط: به رابطه و اتصال بین دو یا چند عنصر در یک شبکه یا ساختار گرافی اشاره دارد. این مفهوم به نحوه‌ی ارتباط یا ارتباطات بین عناصر می‌پردازد، بدون ارائه‌ی هرگونه تعریف خاصی از گروه یا جامعه.

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

در کل  associationبه رابطه و اتصال بین عناصر در یک شبکه اشاره دارد، در حالی که "community" به گروه‌های عناصر مشابه یا مرتبط درون یک شبکه می‌پردازد که ارتباطات نزدیکی با یکدیگر دارند و به صورت جامعه‌ای در نظر گرفته می‌شوند.

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

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

به عنوان مثال، در شبکه‌های اجتماعی، افرادی که با یکدیگر در ارتباطات نزدیکی هستند، نه تنها ممکن است association داشته باشند به عنوان مثال، دو نفر که یکدیگر را دنبال می‌کنند، بلکه ممکن است به عنوان یک انجمن یا جامعه در نظر گرفته شوند اگر ویژگی‌های مشترک بیشتری نیز داشته باشند، مثلاً علایقیا فعالیت‌های مشابه.

الگوریتم هایassociation

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

چندین الگوریتم برای کشف این ارتباطات و الگوها وجود دارد. برخی از معروف‌ترین الگوریتم‌هایAssociation عبارتند از:

الگوریتم DBSCAN

الگوریتم DBSCAN  یا همان Density Based Spatial Clustering of Applications with Noise رایج ترین الگوریتم خوشه بندی مبتنی بر تراکم می باشد که در مقابل نویز و داده های پرت مقاوم می باشد. همچنین با توجه به ساختار این الگوریتم، جهت شناسایی الگوهای پیچیده و غیرکروی مورد استفاده قرار می گیرد.

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

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

دو پارامتر اصلی برای اجرای الگوریتم

دو پارامتر اصلی برای اجرای الگوریتم وجود دارد:

eps یا شعاع همسایگی: فاصله ای که برای تعریف همسایگی به کار می رود. اگر دو رکورد دارای فاصله کمتر از آن باشند، نقاط همسایه در نظر گرفته می شود.

minPts: حداقل تعداد همسایه در محدوده یک شعاع تعریف شده جهت قرار گیری در یک خوشه با توجه به پارامترهای تعریف شده، سه گروه از داده ها قابل تعریف است:

نقاط مرکزی Core Point: نقاطی از داده ها که در شعاع همسایگی آنها حداقل به تعداد minPts همسایه وجود داشته باشد.

Border Points نقاط مرزی: همسایگانی از نقاط مرکزی که قابلیت تبدیل به نقاط مرکزی ندارند.

نقاط پرت Noise Points: نقاطی که در همسایگی هیچ نقطه مرکزی نیستند.