Генетический алгоритм для решения СЛАУ — это эвристический алгоритм поиска, который используется для решения задач оптимизации и моделирования методом случайного подбора, комбинирования и вариации искомых параметров с применением механизмов, являющихся аналогами естественного отбора в природе.
Введение
Процесс решения некоторых математических задач, связанных с физикой, таких как, задачи гидро- и газодинамики, электромагнитных полей, уравнения Максвелла, Навье-Стокса и другие, методами конечных элементов (FEM) и конечных объемов (FVM) часто ведёт к системам линейных алгебраических уравнений (СЛАУ) с разреженными матрицами больших размерностей, которые обычно выступают как несимметричные.
Эффективной методикой решения задач с большими размерностями могут считаться многопроцессорные вычислительные системы, тем не менее, необходимая реализация классических методик потребует их специализированной адаптации и осуществления связанных с этим исследований.
Генетический алгоритм, применяющий метод обобщенных минимальных невязок GMRES для определения функции приспособленности (фитнес-функции), считается очень эффективным средством решения СЛАУ с несимметричной матрицей. Основными достоинствами генетического алгоритма могут считаться следующие аспекты:
- Генетический алгоритм показал свой уровень эффективности при решении дискретных экстремальных задач, которые плохо поддаются решению стандартными методиками.
- Стохастика, применяемая генетическим алгоритмом, предоставляет возможность не пропустить решения, которые не поддаются той или иной эвристике.
- Время вычислений генетических алгоритмов практически для всех приложений фактически имеет линейную зависимость от размеров задачи и количества оптимизируемых параметров.
Генетический алгоритм для решения СЛАУ
Главными проблемами, возникающими при использовании генетических алгоритмов для решения различных задач, являются следующие проблемы:
- Проблема настройки операций скрещивания, мутации и селекции.
- Проблема попадания в локальные минимумы.
- Проблема выбора метода задания критериев останова и выживаемости.
Главной задачей, подлежащей рассмотрению, является определение решения СЛАУ:
Ах = b,
где: A является невырожденной матрицей размерности m х n, ах и b являются векторами, имеющими размерность n х 1, составленными из действительных коэффициентов.
При этом СЛАУ обладает большой размерностью, типа:
$P = NM = 10^9 ... 10^{10}$
или даже сверхбольшой размерностью:
$P = NM > 10^{11}$
Генетические алгоритмы служат для решения оптимизационных задач, в том числе для решения СЛАУ. Причём основой генетического алгоритма является метод случайного поиска. Основным недостатком случайного поиска считается тот факт, что заранее неизвестно, сколько может потребоваться времени для решения поставленной задачи. Для того чтобы исключить подобные временные затраты при решении задачи, могут использоваться методики, которые проявились в биологии и были открыты при изучении эволюции и происхождения видов. Общеизвестно, что в процессе эволюции способны выжить только самые приспособленные особи. Это ведёт к тому, что приспособляемость популяции возрастает, что позволяет ей лучше перенести изменяющиеся условия. Впервые такой алгоритм предложил в 1975-ом году Джон Холланд (John Holland), учёный из Мичиганского университета. Этот алгоритм получил наименование «репродуктивный план Холланда» и был положен в основание фактически любого варианта генетического алгоритма.
Алгоритм Холланда состоит из следующих процедур:
- Генерирование случайным образом популяции, которая состоит из k особей.
- Вычисление целевой функции F(x) (фитнес-функции), то есть, приспособляемость каждой особи популяции. Значение данной функции может определить, насколько хорошо подходит особь, которая описывается данной хромосомой, для разрешения поставленной задачи.
- Выполнение операции селекции.
- Выполнение операции скрещивания, которая состоит из выбора пар для скрещивания. А затем для каждой выбранной пары с заданной вероятностью следует выполнить скрещивание, получить двух потомков и осуществить в популяции замену родителей их потомками.
- Выполнение операции мутации, то есть необходимо с заданной вероятностью изменить гены потомков.
- Если критерий останова ещё не был достигнут, то следует вернуться к шагу два, а в противном случае следует завершить работу.
Рассмотрим настройку алгоритма Холланда для случая задачи решения СЛАУ. Для того чтобы получить большую вычислительную мощность алгоритма и решения СЛАУ с большими размерностями некоторые пункты стандартного алгоритма Холланда могут быть заменены неклассическими и эвристическими. Для решения СЛАУ с большими размерностями не подходит ни одна операция мутации, описанная в работах специалистов. Поэтому следует применять новую модернизированную операцию мутации.
На первом этапе особи стартовой популяции должны генерироваться произвольно, но при условии того, что гены не могут превышать максимальный по модулю элемент матрицы A и вектора b. Данная эвристика используется для повышения вычислительной мощности алгоритма, так как, если генерировать начальные значения в произвольном порядке, то алгоритм может работать лишь на матрицах, размерность которых не превышает десяти. В отдельных случаях матрицы могут быть не просто больших размерностей, а сверхбольших. Для решения СЛАУ с такими размерностями была спроектирована эвристика ограничения выбора. То есть гены вектора решения могут выбираться из интервала (– max(A, b); max(A, b)).
В приведённом алгоритме не предусматриваются какие-либо аналогово-дискретные преобразования исходной задачи, в отличие, к примеру, от алгоритмов, описанных в работах некоторых специалистов. По этой причине гены представляются не битами, а действительными числами.
