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

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

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

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

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

فیلم آموزش برنامه نویسی جاوا Java در فرادرس

کلیک کنید

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

• کمینه‌سازی بی اصطکاک: در «کمینه‌سازی بی اصطکاک» (Frictionless Minimization) نیازی به تغییر دادن یا دستکاری تابع‌های برازش وجود ندارد و می‌توان صرفاً به پیکربندی کلاس Engine پرداخت و بدین ترتیب آماده آغاز نخستین اپلیکیشن شد.
• بدون وابستگی: در ویژگی «بدون وابستگی» (Dependency Free) هیچ کتابخانه شخص ثالث زمان اجرایی برای استفاده از Jenetics مورد نیاز نیست.
• آماده Java 8: در این حالت از عبارت‌های لامبدا و Stream پشتیبانی کامل صورت می‌گیرد.
• چند نخی: در حالت «چند نخی» (Multithreaded) مراحل تکاملی به صورت موازی اجرا می‌شوند.

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

1<dependency>
2    <groupId>io.jenetics</groupId>
3    <artifactId>jenetics</artifactId>
4    <version>3.7.0</version>
5</dependency>

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

2. کاربردهای عملی

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

فیلم آموزش تولباکس الگوریتم ژنتیک متلب در فرادرس

کلیک کنید

2.1 الگوریتم ژنتیک ساده

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

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

بدین ترتیب BitChromosome را با طول 10 می‌سازیم و احتمال داشتن 1-ها را در کروموزوم برابر با 0.5 می‌گیریم. اینک می‌توانیم محیط اجرا را ایجاد کنیم:

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

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

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

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

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

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

1Before the evolution:
2[00000010|11111100]
3After the evolution:
4[00000000|11111111]

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

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

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

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

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

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

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

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

1@Override
2public Function<ISeq<Integer>, Integer> fitness() {
3    return subset -> Math.abs(subset.stream()
4      .mapToInt(Integer::intValue).sum());
5}
6 
7@Override
8public Codec<ISeq<Integer>, EnumGene<Integer>> codec() {
9    return codecs.ofSubSet(basicSet, size);
10}

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

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

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

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

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

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

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

1[85|-76|178|-197|91|-106|-70|-243|-41|-98|94|-213|139|238|219] --> 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1+---------------------------------------------------------------------------+
2|  Time statistics                                                          |
3+---------------------------------------------------------------------------+
4|             Selection: sum=0,039207931000 s; mean=0,003267327583 s        |
5|              Altering: sum=0,065145069000 s; mean=0,005428755750 s        |
6|   Fitness calculation: sum=0,029678433000 s; mean=0,002473202750 s        |
7|     Overall execution: sum=0,111383965000 s; mean=0,009281997083 s        |
8+---------------------------------------------------------------------------+
9|  Evolution statistics                                                     |
10+---------------------------------------------------------------------------+
11|           Generations: 12                                                 |
12|               Altered: sum=7 664; mean=638,666666667                      |
13|                Killed: sum=0; mean=0,000000000                            |
14|              Invalids: sum=0; mean=0,000000000                            |
15+---------------------------------------------------------------------------+
16|  Population statistics                                                    |
17+---------------------------------------------------------------------------+
18|                   Age: max=10; mean=1,792167; var=4,657748                |
19|               Fitness:                                                    |
20|                      min  = 0,000000000000                                |
21|                      max  = 716,684883338605                              |
22|                      mean = 587,012666759785                              |
23|                      var  = 17309,892287851708                            |
24|                      std  = 131,567063841418                              |
25+---------------------------------------------------------------------------+

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

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

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

3. نتیجه‌گیری

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

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

کلیک کنید

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

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

==