الگوریتم‌های تکاملی از دهه 1960 میلادی به عنوان الگوریتم‌های جستجو و بهینه‌سازی معرفی شدند. این الگوریتم‌های تکاملی از مفاهیم زیست‌شناسی تکاملی الهام گرفته و به منظور حل مسائل پیچیده‌ای که با روش‌های سنتی قادر به حل آنها نیستیم، به کار می‌روند. کتابخانه Jenetics در جاوا ابزاری است که برای حل مسائل بهینه‌سازی مختلف با استفاده از الگوریتم‌های تکاملی طراحی شده است. این کتابخانه با استفاده از رابط Stream جاوا پیاده‌سازی شده و به خوبی با بقیه APIهای جاوا سازگاری دارد. در این آموزش به بررسی جزئیات کتابخانه ژنتیک قدرتمند جاوا و نحوه استفاده از آن برای حل مسائل بهینه‌سازی می‌پردازیم.
اصول نظری و مفاهیم کتابخانه Jenetics در جاوا
پیش از آن که به کتابخانه ژنتیک بپردازیم باید با چند مفهوم پایه ژنتیکی آشنا شویم. Jenetics از چند اصل نظری مهم در الگوریتم‌های تکاملی استفاده می‌کند:
- انتخاب طبیعی: فرآیندی که در آن افراد قوی‌تر از یک جمعیت باقی می‌مانند و باقی جمعیت از بین می‌روند.
- بازتولید: فرآیند تولید فرزندان جدید از والدین انتخاب شده در فرایند انتخاب طبیعی.
- جهش: ایجاد تغییرات تصادفی در ژن‌ها برای افزایش تنوع ژنتیکی.
- ترکیب: ترکیب ژن‌های دو والد برای تولید فرزندان جدید.
اجزای زیر نیز از ضروریات آشنایی با الگوریتم ژنتیک و درک بهتر آن به شمار می‌روند:
- کروموزوم‌ها و ژن‌ها
در Jenetics کروموزوم‌ها در واقع مجموعه‌ای از ژن‌ها هستند که نمایانگر راه‌حل‌های ممکن برای مسئله بهینه‌سازی هستند. هر ژن یک مقدار مشخص را در خود نگه می‌دارد که به آن “آلل” گفته می‌شود. Jenetics انواع مختلفی از ژن‌ها و کروموزوم‌ها را پشتیبانی می‌کند، مانند BitGene، DoubleGene، IntegerGene و غیره.
- تابع برازش (Fitness Function)
تابع برازش، معیاری برای ارزیابی کیفیت راه‌حل‌های موجود است. با این تابع میزان سازگاری هر فرد (هر کروموزوم) با مسئله مورد نظر را محاسبه می‌کنیم. در واقع، تابع برازش به الگوریتم کمک می‌کند تا از بین تمامی راه‌حل‌های ممکن بهترین راه‌حل‌ها را شناسایی کند.
- محیط تکاملی (Evolution Engine)
محیط تکاملی یا همان Evolution Engine، مسئول اجرای فرآیند تکامل است. این محیط تنظیمات مختلفی مانند تعداد نسل‌ها، اندازه جمعیت، احتمال جهش و ترکیب و غیره را در اختیار ما می‌گذارد. Jenetics با استفاده از این تنظیمات، فرآیند تکامل را به صورت خودکار مدیریت می‌کند.
ساختار کلی Jenetics
Jenetics یک کتابخانه مبتنی بر الگوریتم‌های تکاملی است که از مکانیزم‌های الهام گرفته از تکامل بیولوژیکی مانند بازتولید، جهش، ترکیب و انتخاب استفاده می‌کند. این کتابخانه ویژگی‌هایی دارد که آن را برای استفاده در مسائل بهینه‌سازی بسیار مناسب می‌کند:
- بهینه‌سازی بدون اصطکاک: نیازی به تغییر یا تنظیم تابع برازش نیست؛ تنها لازم است تنظیمات کلاس Engine را تغییر بدهیم و سپس می‌توانیم برنامه خود را شروع کنیم.
- بدون وابستگی به کتابخانه‌های خارجی: برای استفاده از Jenetics نیازی به هیچ کتابخانه شخص ثالثی در زمان اجرا نداریم.
- پشتیبانی کامل از جاوا 8: این کتابخانه از Stream و اکسپرشن‌های lambda به طور کامل پشتیبانی می‌کند.
- چند نخی: یعنی مراحل تکاملی می‌توانند به صورت موازی اجرا شوند.
پیشنهاد مطالعه: مدت زمان یادگیری جاوا برای حرفه‌ای شدن در آن
شروع کار با کتابخانه Jenetics در جاوا
در مرحله اول محیط را برای شروع اولین پروژه Jenetics آماده می‌کنیم. برای استفاده از Jenetics، ابتدا باید وابستگی‌های لازم را در فایلpom.xml پروژه اضافه کنیم:
io.jenetics jenetics 3.7.0
- برای دریافت آخرین نسخه Jenetics می‌توانید از این لینک به سایت Maven Central مراجعه کنید.
موارد استفاده از Jenetics
برای تست ویژگی‌های Jenetics، می‌توانیم دو مسئله بهینه‌سازی معروف را انتخاب کنیم و به حل آنها بپردازیم. در این مقاله، سه مسئله بهینه‌سازی از ساده تا پیچیده را بررسی می‌کنیم:
- یک مسئله الگوریتم باینری ساده
- مسئله جمع زیرمجموعه‌ها
- مسئله کوله پشتی (knapsack problem)
الگوریتم ژنتیک ساده
فرض کنید میخواهیم مسئله ساده‌ای را حل کنیم که در آن باید موقعیت بیت‌های 1 را در کروموزوم‌های متشکل از بیت‌های 0 و 1 بهینه‌سازی کنیم.
- ابتدا باید فکتوری مناسبی برای مسئله تعریف کنیم:
Factory<Genotype> gtf = Genotype.of(BitChromosome.of(10, 0.5));
در اینجا یک BitChromosome با طول 10 که احتمال داشتن بیت‌های 1 در آن برابر با 0.5 است ایجاد کردیم.
- اکنون باید محیط اجرای الگوریتم را ایجاد کنیم:
Engine<BitGene, Integer> engine = Engine.builder(SimpleGeneticAlgorithm::eval, gtf).build();
- متد eval تعداد بیت‌های 1 را برمی‌گرداند:
private Integer eval(Genotype gt) {
return gt.getChromosome().as(BitChromosome.class).bitCount();
}
- در مرحله آخر فرایند تکامل را شروع کرده و نتایج را جمع‌آوری می‌کنیم:
Genotype result = engine.stream() .limit(500) .collect(EvolutionResult.toBestGenotype());
- نتیجه نهایی به این شکل خواهد بود:
Before the evolution [00000010|11111100] After the evolution [00000000|11111111]
در اینجا ما توانستیم موقعیت بیت‌های 1 را در بیت‌کروموزومی با طول 10 بهینه‌سازی کنیم.
مسئله جمع زیر مجموعه
یک مورد استفاده مهم دیگر از Jenetics حل «مسئله جمع زیرمجموعه» است. به طور خلاصه، چالش در اینجا این است که یک مجموعه از اعداد صحیح به ما داده شده و حالا ما باید یک زیرمجموعه غیرتهی از آنها را پیدا کنیم که مجموع اعضای آن صفر باشد. در Jenetics برای حل چنین مسائلی رابط‌های از پیش تعریف شده‌ای وجود دارد که از آنها استفاده می‌کنیم:
public class SubsetSum implements Problem<ISeq, EnumGene, Integer> {
// implementation
}
همانطور که می‌بینیم، ما مسئله Problem<T, G, C> را پیاده‌سازی می‌کنیم که سه پارامتر دارد:
- <T> : نوع آرگومان تابع برازش مسئله، که در اینجا یک دنباله ثابت و مرتب از اعداد صحیح ISeq<Integer> است.
- <G> : نوع ژنی که موتور تکامل با آن کار می‌کند، که در اینجا ژن‌های شمارشی صحیح EnumGene<Integer> است.
- <C> : نوع نتیجه تابع برازش که در اینجا یک عدد صحیح است.
همانطور که در زیر می‌بینید برای استفاده از رابط Problem<T, G, C>، باید دو متد را بازنویسی کنیم:
@Override
public Function<ISeq, Integer> fitness() {
return subset -> Math.abs(subset.stream()
.mapToInt(Integer::intValue).sum());
}
@Override
public Codec<ISeq, EnumGene> codec() {
return codecs.ofSubSet(basicSet, size);
}
در متد اول، تابع برازش خود را تعریف می‌کنیم، در حالی که متد دوم کلاسی است که شامل متدهای فکتوری برای ایجاد رمزگذاری‌های مسائل رایج است، به عنوان مثال، برای پیدا کردن بهترین زیرمجموعه با اندازه ثابت از یک مجموعه اولیه داده شده، مانند مسئله فعلی که انتخاب کرده‌ایم.
حالا می‌توانیم به مسئله اصلی بپردازیم.
- در ابتدا، زیرمجموعه مورد نیاز برای استفاده در مسئله را به شکل زیر ایجاد می‌کنیم:
SubsetSum problem = of(500, 15, new LCG64ShiftRandom(101010));
در اینجا ما داریم از تولیدکننده LCG64ShiftRandom ارائه شده توسط Jenetics استفاده می‌کنیم.
- در مرحله بعدی، انجین حل مسئله خود را می‌سازیم:
Engine<EnumGene, Integer> engine = Engine.builder(problem) .minimizing() .maximalPhenotypeAge(5) .alterers(new PartiallyMatchedCrossover<>(0.4), new Mutator<>(0.3)) .build();
ما سعی می‌کنیم با تنظیم سن فنوتیپ و تغییرگرهایی که برای تغییر نوادگان استفاده می‌شوند نتیجه را به حداقل برسانیم (نتیجه مدنظر ما 0 خواهد بود).
- در این مرحله می‌توانیم نتیجه را بدست بیاوریم:
Phenotype<EnumGene, Integer> result = engine.stream() .limit(limit.bySteadyFitness(55)) .collect(EvolutionResult.toBestPhenotype());
توجه داشته باشید که ما ازbySteadyFitness() استفاده می‌کنیم که یک شرط را برمی‌گرداند: اینکه اگر فنوتیپ بهتری پس از تعداد مشخصی از نسل‌ها یافت نشد، جریان تکامل را قطع کرده و بهترین نتیجه را جمع‌آوری کند. اگر خوش‌شانس باشیم و راه‌حلی برای مجموعه‌ای که به طور تصادفی ایجاد شده وجود داشته باشد، چیزی شبیه به این خواهیم داشت.
[85|-76|178|-197|91|-106|-70|-243|-41|-98|94|-213|139|238|219] --> 0
در غیر این صورت، مجموع زیرمجموعه برابر با 0 نخواهد بود.
پیشنهاد مطالعه: ساختمان داده Collection در جاوا: راهنمای جامع
مسئله کوله‌پشتی با کتابخانه Jenetics در جاوا
با کتابخانه Jenetics در جاوا می‌توانیم مسائل پیچیده‌تری مثل مسئله کوله‌پشتی را نیز حل کنیم. این مسئله به شکل زیر است:
ما فضای محدودی در کوله‌پشتی خود داریم و میخواهیم آن را با آیتم‌هایی پر کنیم. هر آیتم اندازه و قیمت مخصوص به خود را دارد. باید تصمیم بگیریم که کدام اقلام را درون کوله‌پشتی قرار بدهیم تا وسایل داخل کوله‌پشتی مجموعا کمترین اندازه و بیشترین قیمت ممکن را داشته باشند.
- با تعریف اندازه کوله‌پشتی و تعداد آیتم‌ها شروع کنیم:
int nItems = 15; double ksSize = nItems * 100.0 / 3.0;
- در مرحله بعدی، یک آرایه تصادفی از اشیاء KnapsackItem (که توسط فیلدهای اندازه و قیمت تعریف شده‌اند) تولید می‌کنیم و اقلام را به صورت تصادفی با استفاده از روش جایگزینی اول، درون کوله‌پشتی قرار می‌دهیم:
KnapsackFF ff = new KnapsackFF(Stream.generate(KnapsackItem::random) .limit(nItems) .toArray(KnapsackItem[]::new), ksSize);
- سپس، باید موتور را ایجاد کنیم:
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();
هنگام حل این مسئله باید به این نکات توجه کنید:
- اندازه جمعیت 500 است.
- نسل‌ها از طریق انتخاب‌های تورنومنت و چرخ رولت انتخاب می‌شوند.
- همانطور که در مسئله قبلی دیدیم، نیاز است که تغییرگرها را برای نوادگان تازه ایجادشده تعریف کنیم.
یکی دیگر از ویژگی‌های بسیار مهم Jenetics این است که به راحتی می‌توانیم تمام آمار را از کل مدت زمان شبیه‌سازی جمع‌آوری کنیم.
- این کار را با استفاده از کلاس EvolutionStatistics انجام می‌دهیم:
EvolutionStatistics<Double, ?> statistics = EvolutionStatistics.ofNumber();
- در نهایت، شبیه‌سازی‌ها را اجرا می‌کنیم:
Phenotype<BitGene, Double> best = engine.stream() .limit(bySteadyFitness(7)) .limit(100) .peek(statistics) .collect(toBestPhenotype());
دقت کنید که آمار ارزیابی را باید بعد از هر نسل به‌روزرسانی کنیم، که به 7 نسل پایدار و در مجموع حداکثر 100 نسل محدود شده است. با وجود جزئیات بیشتر، دو سناریوی ممکن است اتفاق بیفتد:
- در کمتر از 100 نسل به 7 نسل پایدار می‌رسیم و شبیه‌سازی متوقف می‌شود.
- نمی‌توانیم در کمتر از 100 نسل به 7 نسل پایدار برسیم، بنابراین شبیه‌سازی به دلیل محدودیت دوم است که متوقف می‌شود.
داشتن محدودیت برای حداکثر تعداد نسل‌ها خیلی مهم است، زیرا در صورت تعیین نکردن محدودیت نسل‌ها، شبیه‌سازی ممکن است در زمان معقولی متوقف نشوند.
- نتیجه نهایی حاوی اطلاعات زیادی است:
+---------------------------------------------------------------------------+ | 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 | +---------------------------------------------------------------------------+
در بهترین سناریو، در این زمان خاص ما توانستیم اقلامی با مجموع ارزش 716.68 را داخل کوله پشتی قرار بدهیم. در بالا می‌توانید آمار دقیق تکامل را ببینید.
پیشنهاد مطالعه: رشته ها در جاوا: راهنمای کامل استرینگ در جاوا
چگونه تست کنیم؟
فرآیند تست راه حل نسبتاً ساده است. فقط باید فایل اصلی مرتبط با مسئله را باز کنید و الگوریتم را اجرا کنید. پس از اینکه ایده کلی را به خوبی درک کردید، می‌توانیم شروع به بازی با پارامترها کنید و به تسلط بیشتری برسید.
کلام پایانی
Jenetics در جاوا نوعی کتابخانه قدرتمند است که می‌توانیم از آن برای حل مسائل بهینه‌سازی با استفاده از الگوریتم‌های تکاملی بهره ببریم. ویژگی‌های برجسته‌ای مانند پشتیبانی کامل از جاوا 8، چند نخی بودن و عدم وابستگی به کتابخانه‌های خارجی، این کتابخانه را به ابزاری مناسب برای توسعه‌دهندگان جاوا که به دنبال حل مسائل پیچیده بهینه‌سازی هستند، تبدیل کرده است. با استفاده از این کتابخانه می‌توانید به راحتی مسائل مختلفی مانند بهینه‌سازی موقعیت بیت‌ها در کروموزوم و مسئله جمع زیرمجموعه و حتی مسائل پیچیده‌ای مانند مسئله کوله پشتی را حل کنید.
ما اینجا در مکتوب، ده‌ها آموزش مختلف در زمینه برنامه‌نویسی جاوا داریم که می‌توانید با استفاده از آنها دانش برنامه‌نویسی‌تان را تقویت کنید و به یک متخصص برنامه‌نویسی تبدیل شوید. بعلاوه، با شرکت در دوره‌های آموزش جاوا و آموزش برنامه نویسی مکتب خونه و کسب گواهی معتبر، می‌توانید مهارت‌های خود را به شکل عملی تقویت کنید و در بازار کار از آنها بهره ببرید.
