یک نسخه دودویی از الگوریتم پیچک برای حل مسائل کوله پشتی صفر-یک

مقالات آماده انتشار

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشکده فناوری اطلاعات و مهندسی کامپیوترـ دانشگاه شهید مدنی آ‌ذربایجان ـ تبریز-ایران

2 دانشکده فناوری اطلاعات و مهندسی کامپیوترـ دانشگاه شهید مدنی آ‌ذربایجان ـ تبریز-ایران-

3 گروه مهندسی کامپیوتر، دانشگاه ملایر، ملایر، ایران

چکیده

چکیده: در این پژوهش، نسخه‌ای باینری از الگوریتم الهام‌گرفته از رشد پیچک (IVY) با هدف حل مسأله کوله‌پشتی صفر و یک طراحی و ارزیابی شده است. مسأله کوله‌پشتی یکی از مسائل کلاسیک بهینه‌سازی ترکیبیاتی است که در حوزه‌های مختلفی از جمله تخصیص منابع، زمان‌بندی و برنامه‌ریزی پروژه کاربرد دارد. حل این مسأله با توجه به پیچیدگی نمایی فضای جستجو، نیازمند استفاده از الگوریتم‌های مؤثر و کارآمد است. نسخه BiIVY با ترکیب مکانیزم رشد جهت‌دار، تابع جریمه و الگوریتم ترمیم ویژه، قابلیت یافتن پاسخ‌های بهینه با تعداد تکرار کمتر نسبت به الگوریتم‌های مرسوم را فراهم می‌کند. پارامترهای الگوریتم با توجه به منابع پیشین و آزمون‌های آزمایشی تعیین شده‌اند. کارایی BiIVY روی ۲۵ مجموعه داده استاندارد L1–L25 ارزیابی شده و با الگوریتم‌های دودویی گرده‌افشانی گل (BFPA) و الگوریتم سینوسی-کسینوسی دودویی (BSCA) مقایسه گردیده است. نتایج آزمون میانگین رتبه فریدمن نشان می‌دهد که BiIVY در اکثر موارد از لحاظ کل سود و تعداد تکرار عملکرد بهتری دارد و توانسته پاسخ‌های بهینه یا نزدیک به بهینه را با تعداد تکرار کمتر ارائه دهد، که اثربخشی و توانایی الگوریتم پیشنهادی را در حل مسائل ترکیبیاتی پیچیده نشان می‌دهد.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

A binary version of the Ivy algorithm for solving zero-one knapsack

نویسندگان [English]

  • Saeedeh Mohammadzadeh 1
  • Einollah Pira 2
  • َAlireza Rouhi 1
  • Sajjad Esfandyari 3
1 Faculty of Information Technology and Computer Engineering, Azarbaijan Shahid Madani University, Tabriz, Iran
2 Faculty of Information Technology and Computer Engineering, Azarbaijan Shahid Madani University, Tabriz, Iran
3 Department of Computer Engineering, Malayer University, Malayer, Iran
چکیده [English]

Abstract: In this study, a binary version of the Ivy-inspired algorithm (IVY) was designed and evaluated to solve the 0–1 Knapsack Problem. The Knapsack Problem is a classical combinatorial optimization problem with applications in resource allocation, scheduling, and project planning. Due to the exponential complexity of its search space, efficient and effective algorithms are required to solve it. The BiIVY version combines a directed growth mechanism, a penalty function, and a specialized repair algorithm, enabling it to find higher-quality solutions with fewer iterations compared to conventional algorithms. Algorithm parameters were determined based on previous studies and experimental trials. The performance of BiIVY was evaluated on 25 standard datasets (L1–L25) and compared with Binary Flower Pollination Algorithm (BFPA) and Binary Sine-Cosine Algorithm (BSCA). Friedman mean-rank test results indicate that BiIVY generally outperforms the other algorithms in terms of total profit and iteration count, providing optimal or near-optimal solutions with fewer iterations, which demonstrates the effectiveness and capability of the proposed algorithm in solving complex combinatorial problems.

کلیدواژه‌ها [English]

  • Ivy algorithm
  • knapsack 0-1
  • optimization
  • binary
  • metaheuristic algorithms
محاسبات نرم

مقالات آماده انتشار، پذیرفته شده
انتشار آنلاین از تاریخ 25 بهمن 1404

فایل ها

سابقه مقاله

  • تاریخ دریافت: 19 شهریور 1404
  • تاریخ بازنگری: 30 دی 1404
  • تاریخ پذیرش: 23 بهمن 1404

هم رسانی

ارجاع به این مقاله

آمار