خانه / fd / آشنایی با کتابخانه Jenetics در جاوا — راهنمای کاربردی

آشنایی با کتابخانه Jenetics در جاوا — راهنمای کاربردی

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

  • طراحی الگوریتم ژنتیک در جاوا — به زبان ساده

۱٫ طرز کار کتابخانه Jenetics چگونه است؟

بر اساس مستندات رسمی (+) کتابخانه Jenetics بر مبنای الگوریتم‌های تکاملی نوشته شده در جاوا عمل می‌کند. الگوریتم‌های تکاملی ریشه در علم زیست‌شناسی دارند، چون سازوکارهای آن‌ها از موضوع تکامل یا فرگشت زیست‌شناختی مانند تولیدمثل، جهش، بازترکیب و انتخاب، الهام گرفته است.

Jenetics با استفاده از رابط Stream جاوا پیاده‌سازی شده است و از این رو با بقیه بخش‌های API Stream جاوا به خوبی کار می‌کند. ویژگی‌های اصلی آن به صورت زیر هستند:

کمینه‌سازی بی اصطکاک

در «کمینه‌سازی بی اصطکاک» (frictionless minimization) نیازی به تغییر دادن یا دستکاری تابع‌های برازش وجود ندارد و می‌توان صرفاً به پیکربندی کلاس Engine پرداخت و بدین ترتیب آماده آغاز نخستین اپلیکیشن شد.

بدون وابستگی

در ویژگی «بدون وابستگی» (dependency free) هیچ کتابخانه شخص ثالث زمان اجرایی برای استفاده از Jenetics مورد نیاز نیست.

آماده Java 8

در این حالت از عبارت‌های لامبدا و Stream پشتیبانی کامل صورت می‌گیرد.

چند نخی

در حالت «چند نخی» (multithreaded) مراحل تکاملی به صورت موازی اجرا می‌شوند.

برای استفاده از کتابخانه Jenetics باید وابستگی زیر را به فایل pom.xml اضافه کنیم:

<dependency>     <groupId>io.jenetics</groupId>     <artifactId>jenetics</artifactId>     <version>3.7.0</version> </dependency>

جدیدترین نسخه را می‌توانید در این صفحه Maven Central (+) مشاهده کنید.

۲٫ کاربردهای عملی

برای تست همه ویژگی‌های کتابخانه Jenetics تلاش خواهیم کرد مسائل مختلف و کاملاً مشهور بهینه‌سازی را حل کنیم. برای شروع از الگوریتم باینری ساده آغاز می‌کنیم و مثال‌های خود را با مسئله «کوله‌پشتی» به پایان می‌بریم.

۲٫۱ الگوریتم ژنتیک ساده

فرض کنید نیاز داریم ساده‌ترین مسئله باینری را حل کنیم. در این مسئله باید موقعیت‌های بیت‌های ۱ را در یک کروموزوم که شامل ۰ و ۱ ها است، بهینه‌سازی کنیم. ابتدا باید یک «کارخانه» (factory) مناسب برای این مسئله را تعریف کنیم:

Factory<Genotype<BitGene>> gtf = Genotype.of(BitChromosome.of(10, 0.5));

بدین ترتیب BitChromosome را با طول ۱۰ می‌سازیم و احتمال داشتن ۱-ها را در کروموزوم برابر با ۰٫۵ می‌گیریم. اینک می‌توانیم محیط اجرا را ایجاد کنیم:

Engine<BitGene, Integer> engine    = Engine.builder(SimpleGeneticAlgorithm::eval, gtf).build();

متد ()eval تعداد بیت‌ها را بازگشت می‌دهد:

private Integer eval(Genotype<BitGene> gt) {     return gt.getChromosome().as(BitChromosome.class).bitCount(); }

در مرحله نهایی شروع به تکامل و گردآوری نتایج می‌کنیم:

Genotype<BitGene> result = engine.stream()   .limit(500)   .collect(EvolutionResult.toBestGenotype());

نتیجه نهایی چیزی شبیه زیر خواهد بود:

Before the evolution: [00000010|11111100] After the evolution: [00000000|11111111]

بدین ترتیب موفق شده‌ایم موقعیت ۱-ها را در ژن بهینه‌سازی کنیم.

Jenetics

۲٫۲ مسئله جمع زیرمجموعه‌ها

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

اینترفیس‌های از پیش تعریف شده مختلفی در کتابخانه Jenetics برای چنین مسائلی وجود دارند:

public class SubsetSum implements Problem<ISeq<Integer>, EnumGene<Integer>, Integer> {     // implementation }

همان طور که می‌بینید ما اینترفیس <Problem<T, G, C را پیاده‌سازی کرده‌ایم که سه پارامتر دارد:

  • <T> – نوع آرگومان تابع برازش مسئله است که در مورد مثال فوق یک دنباله از اعداد صحیح با اندازه ثابت، مرتب و «تغییرناپذیر» (immutable) به نام <ISeq<Integer است.
  • <G> – نوع ژن که موتور تکاملی با آن کار می‌کند است و در این مثال ژن‌های صحیح قابل شمارش <EnumGene<Integer هستند.
  • <C> – نوع نتیجه تابع برازش را مشخص می‌کند که در این مثال عدد صحیح است.

برای استفاده از اینترفیس <Problem<T, G, C باید دو متد زیر را override کنیم:

@Override public Function<ISeq<Integer>, Integer> fitness() {     return subset -> Math.abs(subset.stream()       .mapToInt(Integer::intValue).sum()); }   @Override public Codec<ISeq<Integer>, EnumGene<Integer>> codec() {     return codecs.ofSubSet(basicSet, size); }

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

SubsetSum problem = of(500, 15, new LCG64ShiftRandom(101010));

توجه داشته باشید که ما از LCG64ShiftRandom generator استفاده می‌کنیم که از سوی کتابخانه Jenetics ارائه شده است. در مرحله بعد موتور تکامل خودمان را می‌سازیم:

Engine<EnumGene<Integer>, Integer> engine = Engine.builder(problem)   .minimizing()   .maximalPhenotypeAge(5)   .alterers(new PartiallyMatchedCrossover<>(0.4), new Mutator<>(0.3))   .build();

تلاش ما بر این است که نتیجه را کمینه‌سازی کنیم (به طور بهینه نتیجه برابر با ۰ خواهد بود) و این کار از طریق تنظیم سن پروتوتایپ و تغییر مواردی برای ایجاد تغییرات در نسل صورت می‌گیرد. در گام بعدی می‌توانیم نتیجه زیر را به دست بیاوریم:

Phenotype<EnumGene<Integer>, Integer> result = engine.stream()   .limit(limit.bySteadyFitness(55))   .collect(EvolutionResult.toBestPhenotype());

توجه کنید که ما از ()bySteadyFitness استفاده کرده‌ایم. بدین ترتیب یک تخمین بازگشت می‌دهد که در صورت نبود پروتوتایپ بهتر پس از وجود تعداد مفروضی از تولیدها و گردآوری بهترین نتایج، جریان تکاملی می‌شود. اگر خوش‌شانس باشیم و راه‌حلی برای ایجاد تصادفی مجموعه وجود داشته باشد، چیزی مشابه زیر خواهیم داشت:

[۸۵|-۷۶|۱۷۸|-۱۹۷|۹۱|-۱۰۶|-۷۰|-۲۴۳|-۴۱|-۹۸|۹۴|-۲۱۳|۱۳۹|۲۳۸|۲۱۹] --> 0

در غیر این صورت جمع زیرمجموعه‌ها متفاوت از ۰ خواهد بود.

۲٫۳ مسئله تطبیق نخست کوله‌پشتی

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

int nItems = 15; double ksSize = nItems * 100.0 / 3.0;

در گام بعدی یک آرایه تصادفی شامل اشیای KnapsackItem ایجاد می‌کنیم (که بر اساس اندازه و مقدار) تعریف شده‌اند و این آیتم‌ها را به صوت تصادفی با استفاده از متد First Fit درون کوله‌پشتی قرار می‌دهیم.

Engine<BitGene, Double> engine   = Engine.builder(ff, BitChromosome.of(nItems, 0.5))   .populationSize(500)   .survivorsSelector(new TournamentSelector<>(5))   .offspringSelector(new RouletteWheelSelector<>())   .alterers(new Mutator<>(0.115), new SinglePointCrossover<>(0.16))   .build();

چند نکته وجود دارد که باید در اینجا به آن‌ها توجه داشته باشیم:

  • اندازه جمعیت برابر با ۵۰۰ است.
  • نسل ما از طریق گزینش‌های تورنمنت و چرخ رولت انتخاب می‌شوند.
  • همان طور که در زیرمجموعه قبلی انجام دادیم، باید تغییردهنده (Alterer)-هایی را تعریف کنیم که نسل جدیدی را ایجاد می‌کنند.

یک ویژگی مهم دیگر نیز در کتابخانه Jenetics وجود دارد. ما می‌توانیم به سادگی همه آماره و بینش‌ها را در طی کل فرایند شبیه‌سازی گردآوری کنیم. ما قصد داریم این کار را با استفاده از کلاس EvolutionStatistics انجام دهیم:

EvolutionStatistics<Double,?> statistics = EvolutionStatistics.ofNumber();

در نهایت شبیه‌سازی‌ها را اجرا می‌کنیم:

Phenotype<BitGene, Double> best = engine.stream()   .limit(bySteadyFitness(7))   .limit(100)   .peek(statistics)   .collect(toBestPhenotype());

توجه داشته باشید که ما آمارهای تکامل خود را پس از هر ایجاد به‌روزرسانی می‌کنیم که این مقدار محدود به ۷ نسل ثابت و بیشینه ۱۰۰ نسل در مجموع است. برای توضیح بیشتر باید بگوییم که دو سناریوی محتمل وجود دارد:

  • ما ۷ نسل ثابت به دست می‌آوریم و سپس شبیه‌سازی متوف می‌شود.
  • ما نمی‌توانیم ۷ نسل ثابت در کمتر از ۱۰۰ نسل به دست آوریم و از این رو شبیه‌سازی به دلیل محدودیت زمانی متوقف می‌شود.

نکته مهم این است که باید محدودیت نسل‌های بیشینه داشته باشیم، در غیر این صورت شبیه‌سازی‌ها ممکن است در طی یک زمان معقول به پایان نرسند.

نتیجه نهایی شامل اطلاعات زیادی است:

+---------------------------------------------------------------------------+ |  Time statistics                                                          | +---------------------------------------------------------------------------+ |             Selection: sum=0,039207931000 s; mean=0,003267327583 s        | |              Altering: sum=0,065145069000 s; mean=0,005428755750 s        | |   Fitness calculation: sum=0,029678433000 s; mean=0,002473202750 s        | |     Overall execution: sum=0,111383965000 s; mean=0,009281997083 s        | +---------------------------------------------------------------------------+ |  Evolution statistics                                                     | +---------------------------------------------------------------------------+ |           Generations: 12                                                 | |               Altered: sum=7 664; mean=638,666666667                      | |                Killed: sum=0; mean=0,000000000                            | |              Invalids: sum=0; mean=0,000000000                            | +---------------------------------------------------------------------------+ |  Population statistics                                                    | +---------------------------------------------------------------------------+ |                   Age: max=10; mean=1,792167; var=4,657748                | |               Fitness:                                                    | |                      min  = 0,000000000000                                | |                      max  = 716,684883338605                              | |                      mean = 587,012666759785                              | |                      var  = 17309,892287851708                            | |                      std  = 131,567063841418                              | +---------------------------------------------------------------------------+

در این زمان خاص ما توانستیم آیتم‌ها را با مجموع مقدار ۷۱۶٫۶۸ در بهترین سناریو در کوله‌پشتی قرار دهیم. همچنین توانستیم آمارهای تفصیلی تکامل و زمان را به دست بیاوریم.

چگونه تست کنیم؟

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

۳٫ نتیجه‌گیری

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

کد مورد استفاده در این مقاله در این صفحه گیت‌هاب (+) قرار دارد. توجه داشته باشید که در لینک فوق نمونه‌های کد برای چالش‌های بهینه‌سازی بیشتر مانند مسئله Springsteen Record و مسائل فروشنده دوره‌گرد نیز موجود هستند.

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

  • مجموعه آموزش‌های برنامه نویسی جاوا
  • آموزش مبانی علم ژنتیک
  • مجموعه آموزش‌های الگوریتم ژنتیک و محاسبات تکاملی
  • مقدمه‌ای بر الگوریتم ژنتیک به همراه کد جاوا — به زبان ساده
  • آموزش ۲۵ الگوریتم بهینه سازی تکاملی و هوشمند در فرادرس

==

بلی خیر

نوشته آشنایی با کتابخانه Jenetics در جاوا — راهنمای کاربردی اولین بار در مجله فرادرس. پدیدار شد.

درباره ی admin

مطلب پیشنهادی

جستجوی تمام متن در لاراول با استفاده از Scout — به زبان ساده

جستجوی تمام متن یک قابلیت ضروری جهت فراهم ساختن امکان حرکت در میان صفحه‌های وب‌سایت‌های با محتوای گسترده است. در این مقاله، شیوه پیاده‌سازی امکان جستجوی تمام متن را برای یک اپلیکیشن لاراول بررسی می‌کنیم. در واقع ما از کتابخانه Scout لاراول استفاده می‌کنیم که پیاده‌سازی جستجوی تمام متن را به امری ساده و جذاب تبدیل کرده است. مستندات رسمی، کتابخانه Scout لاراول را به صورت زیر توصیف می‌کنند: کتابخانه Scout لاراول یک راه‌حل ساده و مبتنی بر درایور برای افزودن امکان جستجوی تمام متن به مدل‌های Eloquent ارائه می‌کند. Scout با استفاده از «مشاهده‌گرهای مدل» (model observers) به طور خودکار اندیس‌های جستجو را در وضعیتی همگام‌سازی شده با رکوردهای Eloquent حفظ می‌کند. کتابخانه Scout لاراول به مدیریت دستکاری اندیس‌ها در زمان بروز تغییراتی در داده‌های مدل می‌پردازد. جایی که داده‌های اندیس می‌شوند به درایوری وابسته است که برای کتابخانه Scout پیکربندی‌شده است. در حال حاضر کتابخانه Scout از Algolia پشتیبانی می‌کند که یک API موتور جستجوی مبتنی بر کلود است و ما نیز در این مقاله از آن برای نمایش پیاده‌سا..

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *