Làm thế nào để biểu diễn một lịch trình cho vấn đề Timetabler trong thuật toán di truyền?

Question

Đối với thuật toán di truyền thường gen biểu tượng như thế này:

PARENT1: 101101010101001001001001110011100110101011101101 
PARENT2: 010100111011010101110101001001101011001010010110 

nên chéo, đột biến có thể được thực hiện với cơ quan đại diện này như như:

Chọn một điểm chéo:

PARENT1: 1011010101010010 01001001110011100110101011101101 
PARENT2: 0101001110110101 01110101001001101011001010010110 

Thực chéo để sản xuất một đứa trẻ:

CHILD: 1011010101010010 01110101001001101011001010010110 

Mà sau đó sẽ trở thành, một nhiễm sắc thể hoàn toàn mới:

CHILD: 101101010101001001110101001001101011001010010110 

Vấn đề của tôi là làm thế nào để đại diện cho một gen lịch trình hàng tuần trong Java?

Các ví dụ được lấy từ bài viết này: http://secretgeek.net/content/bambrilg.pdf

Tôi impelementing vấn đề timetabling này trong Java và muốn đại diện cho

FIGURE 10: An Entire University Timetable 

trong Java.

Answer 1

Mã bên dưới có thể cung cấp cho bạn ý tưởng về cách tiếp cận vấn đề. Một giải pháp (có thể là thời khóa biểu của trường đại học) bao gồm một loạt các phòng đơn. Các phòng đơn này có một mảng 2 chiều, trong đó các cột là ngày và các hàng là giờ. Tôi đặt HOURS thành 16, vì tôi nghĩ vào ban đêm sẽ không có lớp học. Vì vậy, Hour Row 1 sẽ là giờ đầu tiên trong ngày ... có lẽ từ 7 đến 8 giờ sáng. Các giá trị của mảng hiển thị lớp nào được đặt.

public class SingleRoom { 
    static final int DAYS = 7; 
    static final int HOURS = 16; 
    . . . 
    private int[][] timetable = new int[DAYS][HOURS]; //0 would say room is not booked, >0 indicates the booked class (english advanced (12), object oriented programming (139), etc..) 
} 

public class Solution { 
    static final int AVAILABLE_ROOMS = 26; 
    . . . 
    private SingleRoom[] university_timetable = new SingleRoom[AVAILABLE_ROOMS];  
} 

đột biến:

thay đổi lớp đột biến - thay đổi lớp khác lớp ngẫu nhiên hoặc bằng không = không đặt phòng

công tắc on/off lớp - nếu một giờ tại một ngày trong một căn phòng cụ thể được đặt, tắt nó nếu nó không được đặt, hãy bật nó với một lớp ngẫu nhiên điều này là để cho thuật toán khả năng không đặt giờ, vì trong biến đổi lớp biến đổi 0 có xác suất thấp được chọn

Các ràng buộc

: sau khi tạo các giải pháp, kiểm tra mọi ràng buộc và giữ các giải pháp hợp lệ các giải pháp hợp lệ mới phải được chèn vào dân số của bạn (giải pháp), nếu chúng tốt hơn cho các giải pháp khác đã có trong dân số của bạn hoặc nếu họ nâng cao sự đa dạng về dân số của bạn

Nhưng trong tài liệu bạn gọi nó là khá tốt mô tả cách triển khai GA cho vấn đề này (bắt đầu với trang 16).

Tôi đã viết một khuôn khổ chung java cho thuật toán tối ưu hóa đa mục tiêu mPOEMS (Tối ưu hóa mẫu đa năng với các bước cải tiến được cải tiến), là một GA sử dụng các khái niệm tiến hóa.

Bạn có thể tìm thấy mã here, nó có thể cung cấp cho bạn một ý tưởng làm thế nào để tiếp cận vấn đề của bạn:

Các giải pháp mà bạn có thể tìm thấy với thuật toán này đã được so sánh trong một công trình khoa học với nhà nước-of-the- thuật toán nghệ thuật SPEA-2 và NSGA, và nó đã được chứng minh rằng thuật toán thực hiện so sánh hoặc thậm chí tốt hơn, tùy thuộc vào số liệu bạn thực hiện để đo lường hiệu suất.

Bạn có thể tìm thấy số here.

nguồn lực bổ sung: luận án của tôi mà áp dụng khuôn khổ này đến vấn đề lựa chọn dự án: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

Các tài liệu của khung: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

mPOEMS giấy trình bày: http://portal.acm.org/citation.cfm?id=1792634.1792653

Trên thực tế với một chút nhiệt tình bạn có thể dễ dàng thích ứng với mã của khuôn khổ chung cho nhu cầu của bạn.

Bạn có viết GA này trong công việc của mình hoặc với tư cách là sinh viên không?