همکاری با الگوریتم کلونی زنبور عسل

با پیوند ارجاع من به رسانه بپیوندید - Applied. Math. Coding

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

بیشتر تکنیک های موجود در AI. یادگیری ماشین نیاز به حل یک مشکل بهینه سازی مداوم دارد. به طور معمول این مشکل بهینه سازی غیر خطی است و با دست قابل حل نیست. ادبیات عظیمی در مورد نوع مشکلات بهینه سازی و روشهای ممکن برای حل کارآمد آنها وجود دارد.

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

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

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

الگوریتم

نام آن "الگوریتم کلونی زنبور عسل" است و الگویی را که در طبیعت درباره زنبورها مشاهده شده است دنبال می کند:

تعداد مشخصی از زنبورهای N به طور تصادفی (یکنواخت) در دامنه قرار می گیرند. هر زنبور عسل یک موقعیت مبتنی بر فعلی را به خاطر می آورد و الگوریتم یک بهترین جهانی را به خاطر می آورد.

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

فاز Onlooker: هنگامی که همه زنبورها جستجوی محلی را انجام داده اند ، آنها توسط یک توزیع طبقه بندی شده W. R. T یک مقدار تناسب اندام جابجا می شوند. با جزئیات ، هر زنبور با محاسبه فاصله مقدار آن به مقدار زنبور عسل فعلی ، تناسب اندام اختصاص داده می شود. بنابراین ، هرچه این فاصله بالاتر باشد ، تناسب اندام بهتر می شود. هر مقدار تناسب اندام که ما به عنوان یک مقوله در نظر می گیریم با تقسیم مقدار تناسب اندام بر اساس مجموع مقادیر تناسب اندام وزن می شود. این یک توزیع (طبقه بندی) از تمام مقادیر تناسب اندام را فراهم می کند و می توانیم نمونه های تصادفی از آن بکشیم. توجه داشته باشید ، هرچه تناسب اندام بالاتر باشد ، نمونه ای از دسته مربوطه انتخاب می شود. انجام این کار N بار ، که در واقع به N Times انتخاب برخی از زنبورها کمک می کند ، مکان جدیدی را برای هر زنبور پیدا می کنیم. به این ترتیب ، هرچه مقدار تناسب اندام یک مکان بهتر باشد ، زنبورهای بیشتری به آنجا اختصاص می یابد.

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

موارد فوق چندین بار به منظور بهبود بهینه جهانی یافت شده تکرار می شود.

علاوه بر این روش بسیار پایدار است ، برای ابعاد بالا کار می کند ، نیاز به عملکرد فقط مداوم دارد و اجرای آن بسیار آسان است.

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

بنابراین ، در مواردی که یک راه حل بسیار دقیق از آن حداقل جهانی مورد نیاز است ، این روش بهترین استفاده را با اجازه دادن به آن نقطه و سپس پیگیری با یک شیب تند و یا تکرار نیوتن برای تولید دقت مورد نظر استفاده می کند.

جزئیات بیشتر از جمله مخترع را می توان در:

پیاده سازی

ما قصد داریم به یک اجرای احتمالی در Rust بپردازیم. برای کسانی که نیاز به بسته بندی کمی در زنگ زدگی دارند ، توصیه می کنم مقدمه کوتاه خود را بخوانید.

به منظور تولید مقادیر تصادفی ، ما Rand Rand را به وابستگی های خود (Cargo. toml) قرار می دهیم:

[وابستگی]رند =

در طول برنامه ، ما از انواع زیر استفاده می کنیم:

use rand:: prelude::Distribution, gs::ThreadRng, thread_g, Rng>;pub struktur params n_bees: usize ،رها_لیمیت: استفاده ،max_iter: استفاده ،>نوع x = vec ؛type Target = dyn Fn(&X) >F64 ؛ساختار زنبور عسل: x ،ارزش: F64 ،not_improved_since: استفاده ،تناسب اندام: F64 ، // فاصله تا بدترین>

بنابراین ، زنبور عسل با موقعیت ، ارزش ، تناسب اندام و چند بار که نتوانسته است ارزش خود را بهبود ببخشد ، توصیف می شود. X فقط یک مکان مناسب برای دامنه است و هدف نوع عملکردی است که می خواهیم به حداقل برسانیم.

در مرحله بعد ، ما برخی از کارکردهای آسان ابزار مورد نیاز را لیست می کنیم:

fn compute_fitness_on_bees (زنبورها: & mut vec) اجازه دهید mord_value = زنبورها [find_worst_bee_idx (زنبورها)]]. مقدار ؛برای زنبور عسل در زنبورها.>>// بهترین موقعیت و ارزش را در بین همه زنبورها برمی گرداندfn find_best_position_and_value(bees: &Vec) >(x ، f64) اجازه دهید best_bee = زنبورها. iter (). min_by (| b1 ، b2 | b1. value. partial_cmp (& b2. value) . unwrap ()). unwrap () ؛(best_bee. position. clone () ، best_bee. value)>// شاخص زنبور را با بالاترین (بدترین) ارزش باز می گرداندfn find_worst_bee_idx(bees: &Vec) >usize bees. iter (). Enumerate (). max_by (| (_ ، b1) ، (_ ، b2) | b1. value. partial_cmp (& b2. value) . unwrap ()). unwrap ().0>// یک نقطه تصادفی در N-DIM ایجاد می کند. فاصله [A ، B] ،// این یک است fn create_random_position(a: &X, b: &X, g: &mut ThreadRng) >x اجازه دهید mut res = vec! [] ؛برای (u ، v) در A. Iter (). zip (b. iter ()) res. push (g. gen_range (*u ..*v)) ؛> سر>

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

// ایجاد زنبورها و قرار دادن آنها به طور تصادفی در [a ، b]fn init_bees(f: &Target, a: &X, b: &X, n_bees: usize) >VEC اجازه دهید mut res = vec! [] ؛اجازه دهید mut g = thread_g () ؛برای _ در 0.. N_BEES اجازه دهید موقعیت = create_random_position (a ، b ، & mut g) ؛res. push (تناسب اندام زنبور عسل: 0. 0 ،not_improved_since: 0 ،مقدار: F (و موقعیت) ،موقعیت ،>); > سر>// اجازه دهید هر زنبور عسل با حرکت یک فاصله تصادفی به یا دور از آن ، به صورت محلی جستجو کند// زنبور تصادفی دیگر.// در همان زمان ، ارزش/موقعیت جهانی را در سطح جهانی به روز نگه دارید.fn do_local_search_phase (F: & Target ،زنبورها: & mut vec ،بهترین_انه: & mut x ،Best_value: & mut f64 ،تبر،ب: و x ،) اجازه دهید mut g = thread_g () ؛برای idx در 0.. bees. len () اجازه دهید mut new_position = زنبورها. get (idx) . unwrap (). posit. clone () ؛اجازه دهید other_bee_idx = g. gen_range (0.. bees. len ()) ؛let position_idx = g. gen_range (0.. new_position. len ()) ؛اجازه دهید phi = g. gen_range (-1. 0.. 1. 0) ؛اجازه دهید x_i_other = زنبورها (other_bee_idx) . unwrap (). Position [position_idx] ؛اجازه دهید x_i = new_position [station_idx] ؛new_position [station_idx] = (x_i + phi * (x_i_other - x_i)). max (a [station_idx]). min (b [position_idx]) ؛اجازه دهید new_value = f (& new_position) ؛اجازه دهید old_value = زنبورها. get (idx) . unwrap (). مقدار ؛اجازه دهید زنبور = زنبورها. get_mut (idx) . unwrap () ؛اگر new_valuebee. value = new_value ؛bee. not_improved_since = 0 ؛>other bee. not_improved_since += 1 ؛> اگر new_value<*best_value *best_value = bee.value; *best_position = bee. position. clone () ؛> >>// توزیع مجدد زنبورها بر روی مکان های دیگر و اولویت بندی مکان ها با// تناسب اندام بالاتر. این کار با ایجاد یک پریشانی طبقه بندی شده بر روی همه انجام می شود// زنبورها.fn do_onlooker_phase (زنبورها: & mut vec) compute_fitness_on_bees (زنبورها) ؛اجازه دهید sum_fitness = زنبورها.اجازه دهید وزنه ها = زنبورها. iter (). map (| زنبور عسل | زنبور عسل / sum_fitness). collect: :() ؛اجازه دهید cartoristor_dist = وزنه برداری :: جدید (و وزنه ها) . unwrap () ؛اجازه دهید mut g = thread_g () ؛برای idx در 0.. bees. len () اجازه دهید other_bee = زنبورها.اجازه دهید new_position = other_bee. position. clone () ؛اجازه دهید new_value = other_bee. value ؛زنبورها [idx] . Position = new_position ؛زنبورها [idx] . Value = new_value ؛>>// اگر مدت طولانی بهبود نیافته است زنبورها را از موقعیت ها رها کنید.// این از به دام انداختن در حداقل محلی جلوگیری می کند.fn do_scout_phase (زنبورها: & mut vec ،dondon_limit: usize ، a: & x ، b: & x ، f: & target) اجازه دهید mut g = thread_g () ؛Bees. iter_mut ().filter(|bee| bee.not_improved_since>down_limit). for_each (| زنبور | اجازه دهید new_position = create_random_position (a ، b ، & mut g) ؛اجازه دهید new_value = f (& new_position) ؛bee. position = new_position ؛bee. value = new_value ؛bee. not_improved_since = 0 ؛>);>

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

pub fn optimize(f: &Target, a: &X, b: &X, params: Params) >(x ، f64) اجازه دهید زنبور عسل = init_bees (f ، a ، b ، params. n_bees) ؛let (mut best_position ، mut best_value) = find_best_position_and_value (& زنبورها) ؛برای _ در 0.. params. max_iter do_local_search_phase (F ، & Mut Bees ، & mut best_position ، & mut best_value ، a ، b) ؛do_onlooker_phase (& زنبورهای متود) ؛do_scout_phase (و زنبورهای متود ، params. Abandon_limit ، a ، b ، f) ؛> (Best_position ، best_value)>

من به عنوان یک تابع تست ، من از عملکرد Ackley استفاده می کنم (اینجا را ببینید) که تابعی با حداقل محلی است:

fn main () اجازه دهید ackley_fn = | x: & x |-20. 0 * f64 :: exp (-0. 2 * f64 :: sqrt (0. 5 * (x [0] * x [0] + x [1] * x [1]))) - f64 :: exp (0. 5 * (f64 :: cos (2. 0 * pi * x [0]) + f64 :: cos (2. 0 * pi * x [1])) + E + 20. 0>; println! "<>"، ackley_fn (& vec! [0. 0 ، 0. 0])) ؛ // این حداقل است اجازه دهید params = params n_bees: 200 ،رها_لیمیت: 20 ،max_iter: 500 ،>; println! ("", Optimize (& ackley_fn ، & vec! [ -5. 0 ، -5. 0] ، & Vec! [5. 0 ، 5. 0] ، پارامترها));>

([0. 007315634561002593 ، 9. 547793830446227E-5] ، 0. 02211822639045735)

ممکن است کل کد را برای بازی در اینجا پیدا کنید.