Инновационный способ планирования полетов спутников на основе генетических алгоритмов и имитации отжига и соответствующий планировщик полетов

1. Способ (1) планирования полетов спутников, включающий в себя этапы, на которых:
а) создают (105) исходные планы-графики на основе вводимых запросов, связанных с задачами, подлежащими выполнению в течение заданного периода времени одним или несколькими спутниками дистанционного зондирования; причем в каждом из упомянутых исходных планов-графиков запланированы соответствующие задачи, которые не конфликтуют друг с другом во времени и в использовании спутниковых ресурсов спутника (спутников) дистанционного зондирования; и причем каждая из задач, подлежащих выполнению, запланирована по меньшей мере в одном из исходных планов-графиков;
b) применяют (108) основанную-на-генетическом-алгоритме обработку к исходным планам-графикам для создания основанного-на-генетическом-алгоритме плана-графика, который
- глобально оптимизирован относительно заданных целей полета, и
- соответствует заданным ограничениям, связанным с ресурсами спутников, с задачами, подлежащими выполнению, и с заданным периодом времени; и
c) применяют (109) основанную-на-имитации-отжига обработку к основанному-на-генетическом-алгоритме плану-графику для создания основанного-на-имитации-отжига плана-графика,
- который соответствует заданным целям полета,
- который соответствует заданным ограничениям, и
- в котором запланировано большее число задач, чем в основанном-на-генетическом-алгоритме плане-графике;
причем этап b) включает в себя этап, на котором выполняют основанную-на-генетическом-алгоритме итерационную процедуру, содержащую этапы, на которых:
на первой основанной-на-генетическом-алгоритме итерации,
- выбирают (202, 203) подмножество исходных планов-графиков на основе заданных целей полета, и
- применяют методы скрещивания (205), мутации (206) и отбора (207), основанные на соответствующих заранее заданных генетических эволюционных факторах, к выбранному подмножеству исходных планов-графиков для создания развитых планов-графиков, соответствующих заданным ограничениям;
на каждой основанной-на-генетическом-алгоритме итерации, следующей за первой основанной-на-генетическом-алгоритме итерацией,
- выбирают (202, 203), на основе заданных целей полета, подмножество развитых планов-графиков, созданных на предыдущей основанной-на-генетическом-алгоритме итерации, и
- применяют методы скрещивания (205), мутации (206) и отбора (207) к выбранному подмножеству развитых планов-графиков, созданных на предыдущей основанной-на-генетическом-алгоритме итерации, для создания новых развитых планов-графиков, соответствующих заданным ограничениям;
причем упомянутый этап b) дополнительно включает в себя этапы, на которых:
- останавливают (208, 209) выполнение основанной-на-генетическом-алгоритме итерационной процедуры, когда удовлетворяются заданные связанные-с-генетическим-алгоритмом критерии остановки; и
- автоматически выбирают, среди развитых планов-графиков, созданных на последней выполненной основанной-на-генетическом-алгоритме итерации, развитый план-график, который лучше всего соответствует заданным целям полета;
причем способ (1) планирования полетов спутников дополнительно включает в себя этапы, на которых:
- вычисляют (103) матрицу пересечений, представляющую конфликты во времени и в использовании ресурсов спутников задач, подлежащих выполнению в течение заданного периода времени;
- вычисляют (103) сложность плана на основе матрицы пересечений; и
- вычисляют (104, 104а) заданные связанные-с-генетическим-алгоритмом критерии остановки на основе матрицы пересечений;
и причем исходные планы-графики создают (105) на основе матрицы пересечений.
2. Способ планирования полетов спутников по п. 1, в котором этап с) включает в себя этап, на котором выполняют основанную-на-имитации-отжига итерационную процедуру, содержащую этапы, на которых:
на первой основанной-на-имитации-отжига итерации,
- выбирают (302), согласно одной или нескольким заранее заданным функциям вероятности, задачу, не запланированную в основанном-на-генетическом-алгоритме плане-графике,
- идентифицируют (303) окрестность выбранной задачи, причем идентифицированная окрестность включает в себя множество конфликтующих задач, не запланированных в основанном-на-генетическом-алгоритме плане-графике,
- выполняют (304) перестановки конфликтующих задач в идентифицированной окрестности,
- применяют (305, 306, 307, 308) метод имитации отжига к результатам выполненных перестановок для нахождения задач, которые
- не запланированы в основанном-на-генетическом-алгоритме плане-графике,
- являются планируемыми вместе с задачами, уже запланированными в упомянутом основанном-на-генетическом-алгоритме плане-графике,
- соответствуют заданным целям полета, и
- соответствуют заданным ограничениям, и
- создают план-график, включающий в себя найденные задачи;
на каждой основанной-на-имитации-отжига итерации, следующей за первой основанной-на-имитации-отжига итерацией,
- выбирают (302), согласно заранее заданной функции (функциям) вероятности, дополнительную задачу, не запланированную в плане-графике, созданном на предыдущей основанной-на-имитации-отжига итерации,
- идентифицируют (303) окрестность дополнительной выбранной задачи, причем идентифицированная окрестность включает в себя множество конфликтующих задач, не запланированных в плане-графике, созданном на предыдущей основанной-на-имитации-отжига итерации,
- выполняют (304) перестановки конфликтующих задач в идентифицированной окрестности,
- применяют (305, 306, 307, 308) метод имитации отжига к результатам выполненных перестановок для нахождения задач, которые
- не запланированы в плане-графике, созданном на предыдущей основанной-на-имитации-отжига итерации,
- являются планируемыми вместе с задачами, уже запланированными в упомянутом плане-графике, созданном на предыдущей основанной-на-имитации-отжига итерации,
- соответствуют заданным целям полета, и
- соответствуют заданным ограничениям, и
- создают новый план-график, включающий в себя найденные задачи;
причем этап с) дополнительно включает в себя этап, на котором останавливают (309, 310) выполнение основанной-на-имитации-отжига итерационной процедуры, когда удовлетворены заданные связанные-с-имитацией-отжига критерии остановки;
и причем основанный-на-имитации-отжига план-график является планом-графиком, созданным на последней выполненной основанной-на-имитации-отжига итерации.
3. Способ планирования полетов спутников по п. 2, дополнительно включающий в себя этап, на котором вычисляют (104, 104b) заданные связанные-с-имитацией-отжига критерии остановки на основе матрицы пересечений.
4. Способ планирования полетов спутников по любому из предшествующих пунктов, в котором заданные цели полета математически представлены глобальной функцией стоимости, вычисляемой на основе нескольких локальных функций стоимости, основанных на заданных ограничениях.
5. Система (4) обработки для систем наблюдения Земли, включающих в себя один или несколько спутников дистанционного зондирования, причем упомянутая система (4) обработки запрограммирована выполнять способ (1) планирования полетов спутников по любому предшествующему пункту.
6. Компьютерный программный продукт, содержащий одну или несколько частей программного кода, которые являются исполняемыми системой обработки и исполняются таким образом, что они предписывают системе обработки выполнять способ (1) планирования полетов спутников по любому из пп. 1-4.