code:ga_scheduling
no way to compare when less than two revisions
Differences
This shows you the differences between two versions of the page.
Previous revisionNext revision | |||
— | code:ga_scheduling [2009/01/16 13:50] – pkubanek | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== GA Scheduling organization ====== | ||
+ | Algorithm and ideas used for scheduling are described in [[http:// | ||
+ | |||
+ | The algorithm mention constraints and objectives. Constrains method return number of constraint violations and the algorithm tries to minimize them, providing schedule with zero constraint violations. So far there are not soft and hard constraint, and implementation of them to scheduling can be an interesting topics. The algorithm search for maximal values of the objective functions. | ||
+ | |||
+ | Important is to remember that lower constraint violation value means better schedule, and higher objective function value means better schedule. If you come to objective which naturally produces better schedules when lower value is calculated, you can easily change function by using //1/f(x)// instead. | ||
+ | |||
+ | In order to use GA scheduling, you will need to fill in database. You will also find it useful to use //pyrts2// to visualise schedule, so you will be able to see how scheduling algorithm behaves. | ||
+ | |||
+ | ===== Database setup ===== | ||
+ | |||
+ | //Note: Currently you need to build database from REL_0_8_0 branch. See bellow how to retrieve it.// | ||
+ | |||
+ | You need to fill **tickets** and **accounts** tables. | ||
+ | |||
+ | ^ Field name ^ Description ^ | ||
+ | | schedticket_id | ||
+ | | tar_id | ||
+ | | account_id | ||
+ | | obs_num | ||
+ | | sched_from | ||
+ | | sched_to | ||
+ | | sched_interval_min | interval | ||
+ | | sched_interval_max | interval | ||
+ | |||
+ | ===== Using pyrts2 to preview schedules ===== | ||
+ | |||
+ | |||
+ | ====== Obtaining and modifying code ====== | ||
+ | |||
+ | The GA scheduler code currently lives only in [[http:// | ||
+ | |||
+ | <code bash> | ||
+ | svn co https:// | ||
+ | </ | ||
+ | |||
+ | Most of functionality you are interested in is located in [[http:// | ||
+ | |||
+ | ===== Adding a new constraint ===== | ||
+ | |||
+ | To add a new constraint, you should first declare its symbolic name in [[http:// | ||
+ | |||
+ | <code c++> | ||
+ | |||
+ | typedef enum | ||
+ | { | ||
+ | CONSTR_VISIBILITY, | ||
+ | CONSTR_SCHEDULE_TIME, | ||
+ | CONSTR_UNOBSERVED_TICKETS, | ||
+ | CONSTR_OBS_NUM | ||
+ | } constraintFunc; | ||
+ | </ | ||
+ | |||
+ | After you are done, you need to define function which will count constraint violation for you. And you will need to add it to // | ||
+ | |||
+ | <code c++> | ||
+ | /** | ||
+ | * Return constraint function. Constraint is satisfied, if return is = 0. Otherwise | ||
+ | * number of constraint violations is returned. | ||
+ | * | ||
+ | * @param _type Constraint function type. | ||
+ | * | ||
+ | * @return Number of targets which are infeasible with respect to given constraint. | ||
+ | */ | ||
+ | unsigned int getConstraintFunction (constraintFunc _type) | ||
+ | { | ||
+ | switch (_type) | ||
+ | { | ||
+ | case CONSTR_VISIBILITY: | ||
+ | visibilityRatio (); | ||
+ | return unvisible; | ||
+ | case CONSTR_SCHEDULE_TIME: | ||
+ | return violateSchedule (); | ||
+ | case CONSTR_UNOBSERVED_TICKETS: | ||
+ | return unobservedSchedules (); | ||
+ | case CONSTR_OBS_NUM: | ||
+ | return violatedObsNum (); | ||
+ | } | ||
+ | return UINT_MAX; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | and | ||
+ | |||
+ | <code c++> | ||
+ | /** | ||
+ | * Ratio of observations from schedule which are visible. | ||
+ | * | ||
+ | * @return Ration of visible targets. Higher means better schedule. | ||
+ | */ | ||
+ | double visibilityRatio (); | ||
+ | </ | ||
+ | |||
+ | and then in [[http:// | ||
+ | |||
+ | <code c++> | ||
+ | double | ||
+ | Rts2Schedule:: | ||
+ | { | ||
+ | if (!isnan (visRatio)) | ||
+ | return visRatio; | ||
+ | |||
+ | visible = 0; | ||
+ | unvisible = 0; | ||
+ | |||
+ | for (Rts2Schedule:: | ||
+ | { | ||
+ | if ((*iter)-> | ||
+ | visible++; | ||
+ | else | ||
+ | unvisible++; | ||
+ | } | ||
+ | visRatio = (double) visible / size (); | ||
+ | return visRatio; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | The most important is for you inner loop which calculated how much targets in the schedule are unvisible and visible. The first //if// is only syntax sugar for lazy initialization of values, which significantly improves scheduling algorithm speed. Important is iterator loop through members of the schedule, which ask every member if it is visible. // | ||
+ | |||
+ | <code c++> | ||
+ | /** | ||
+ | * Determines schedule target visibility. | ||
+ | * | ||
+ | * @return True is observation is visible. | ||
+ | */ | ||
+ | bool isVisible () | ||
+ | { | ||
+ | // determine if target is visible during whole period | ||
+ | if (getTarget()-> | ||
+ | || getTarget ()-> | ||
+ | || getTarget ()-> | ||
+ | return false; | ||
+ | double minA, maxA; | ||
+ | getTarget ()-> | ||
+ | return minA > 0; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | For definition of //isGood// function, please have a look to [[http:// | ||
+ | |||
+ | After you are done, you shall add new constraint to constraint which will be used in scheduling. This is done in [[http:// | ||
+ | |||
+ | <code c++> | ||
+ | Rts2SchedBag:: | ||
+ | { | ||
+ | // ommited lines.. | ||
+ | |||
+ | constraints.push_back (CONSTR_VISIBILITY); | ||
+ | constraints.push_back (CONSTR_SCHEDULE_TIME); | ||
+ | constraints.push_back (CONSTR_UNOBSERVED_TICKETS); | ||
+ | constraints.push_back (CONSTR_OBS_NUM); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Adding new objective function ===== | ||
+ | |||
+ | Process of adding new objective function is similar to adding new constraint. If you understand how constraint functions are added, you will not have any problems understanding how objectives are added. | ||
+ | |||
+ | You will need to add new objective symbolic name to objFunc enumeration. In [[http:// | ||
+ | |||
+ | <code c++> | ||
+ | const char* getObjectiveName (objFunc obj) | ||
+ | { | ||
+ | const static char* objNames[] = { " | ||
+ | " | ||
+ | return objNames[(int) obj]; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Then procedure is similar - add objective to case in // | ||
+ | |||
+ | And finally add it to // | ||
+ | |||
+ | <code c++> | ||
+ | // fill in parameters for NSGA | ||
+ | objectives.push_back (ALTITUDE); | ||
+ | objectives.push_back (ACCOUNT); | ||
+ | objectives.push_back (DISTANCE); | ||
+ | objectives.push_back (DIVERSITY_TARGET); | ||
+ | |||
+ | </ |
code/ga_scheduling.txt · Last modified: 2009/01/18 00:00 (external edit)