User Tools

Site Tools


code:ga_scheduling

This is an old revision of the document!


GA Scheduling organization

Algorithm and ideas used for scheduling are described in master thesis. Please read this carefully before you will try to add new code.

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.

The GA scheduler code currently lives only in REL_0_8_0 branch. Merging to trunk is expected in a few weeks. To get the code, issue:

svn co https://rts-2.svn.sf.net/svnroot/rts-2/branches/rts-2/REL_0_8_0

Most of functionality you are interested in is located in src/scheduler directory. Here we will mention two changes you will most probably like to to - add a new merit, or new constraint.

Adding a new constraint

To add a new constraint, you should first declare its symbolic name in rts2schedule.h. The constraint shall be added to constraintFunc enumeration:

typedef enum
{
        CONSTR_VISIBILITY,                       // visibility violation - target is not visible
        CONSTR_SCHEDULE_TIME,            // schedule violation - target is scheduled outside its allowed time OR there exists target(s) which was not scheduled while it must be scheduled
        CONSTR_UNOBSERVED_TICKETS,       // number of unobserved tickets - tickets which have time constraint for schedule period, have some numObs left, but were not observed
        CONSTR_OBS_NUM                           // target is observed more times then it should be observed
} 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 getConstraintFunction method. Here is the example how CONSTR_VISIBILITY is defined. In rts2schedule.h you will find:

                /**
                 * 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

                /**
                 * Ratio of observations from schedule which are visible.
                 *
                 * @return Ration of visible targets. Higher means better schedule.
                 */
                double visibilityRatio ();

and then in rts2schedule.cpp you will find that visibility constraint is calculated as:

double
Rts2Schedule::visibilityRatio ()
{
        if (!isnan (visRatio))
                return visRatio;
 
        visible = 0;
        unvisible = 0;
 
        for (Rts2Schedule::iterator iter = begin (); iter != end (); iter++)
        {
                if ((*iter)->isVisible ())
                        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. isVisible is then defined in rts2schedobs.h as:

                /**
                 * Determines schedule target visibility.
                 *
                 * @return True is observation is visible.
                 */
                bool isVisible ()
                {
                        // determine if target is visible during whole period
                        if (getTarget()->isGood (getJDStart ()) == false
                                || getTarget ()->isGood (getJDMid ()) == false
                                || getTarget ()->isGood (getJDEnd ()) == false)
                                return false;
                        double minA, maxA;
                        getTarget ()->getMinMaxAlt (getJDStart (), getJDEnd (), minA, maxA);
                        return minA > 0;
                }

For definition of isGood function, please have a look to src/utilsdb/target.ec.

After you are done, you shall add new constraint to constraint which will be used in scheduling. This is done in rts2schedbag.cpp:

Rts2SchedBag::Rts2SchedBag (double _JDstart, double _JDend)
{
        // 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 rts2schedule.cpp you will need to add new objective to getObjectiveName function:

const char* getObjectiveName (objFunc obj)
{
        const static char* objNames[] = { "VISIBILITY", "ALTITUDE", "ACCOUNT", "DISTANCE",
                "DIVERSITY_TARGET", "DIVERSITY_OBSERVATIONS", "SINGLE"};
        return objNames[(int) obj];
}

Then procedure is similar - add objective to case in Rts2Schedule::getObjectiveFunction, add function to calculate it to Rts2SchedObs class.

And finally add it to objectives in rts2schedbag.cpp:

        // 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.1231675668.txt.gz · Last modified: 2009/01/11 00:00 (external edit)