使用演化演算法對短長度盧比LT code作多對象的最佳化方法

Abstract

短碼長盧比變換碼 (short-length Luby Transform codes)，其為第一個實際可實行的噴泉碼 (fountain codes)，是一種具隨機性並具有強大保護能力的抹除保護碼 (erasure protection codes)，可在多端點傳輸環境中提供可靠的數據串流服務。然而，由於各種應用環境下對於解碼能力有不同的需求，有必要將短碼長盧比變換碼以多目標最佳化方式來設計。因為目前對於短碼長的盧比變換碼還沒有分析方式能估計其解碼表現，若想要設計出需求的解碼表現，唯一可行的方式是採用隨機最佳化方法。 在本研究中，我們將短碼長盧比變換碼的解碼表現設計視為多目標最佳化問題來處理，並實作於一個實際的解碼表現需求問題。為了解決最佳化問題，我們採用四個最先進的多目標最佳化方法，其具有快速、穩定的收斂行為，並代表不同類別的演算法改革，即多目標協方差矩陣適應性演化策略（multi-objective covariance matrix adaptation evolution strategy, MO-CMA-ES），非支配排序遺傳算法-II（non-dominated sorting genetic algorithm-II , NSGA-II），S-公制選擇演化多目標演算法（S-metric selection evolutionary multi-objective algorithm, SMS-EMOA）和穩態多目標協方差矩陣適應性演化策略（steady-state multi-objective covariance matrix adaptation evolution strategy, SS-MO-CMA-ES）。 結果證明，所採用的方法具有產生多目標最佳化問題之帕累托 (Pareto) 最佳解的能力，至於帕累托前的凸性 (convexity) 則不能得到保證。此外，我們的結果顯示在收斂速度方面，NSGA-Ⅱ優於其他三個多目標最佳化方法。

Short-length Luby Transform (SLLT) codes, the first practical implementation of the fountain codes, are powerful randomized erasure protection codes that can be used to provide reliable data streaming services to multiple endpoints. However, due to application dependent and different decoding performance requirements, it is necessary to design SLLT code as multi-objective optimization task. Since, there is no feasible analytical method capable to estimate the decoding performance of these codes if their block length is short while greater than a few hundreds of symbols, the only feasible way to customize their decoding performance is to employ the stochastic optimization methods. In this work, we formulate the customization of SLLT code performance as multi-objective optimization problem and describe one practical SLLT code customization scenario. In order to solve the formulated optimization problem, we employ four state-of-the-art multi-objective optimization methods possessing fast and robust convergence behavior and representing different classes of evolutionary algorithms, i.e., Multi-objective covariance matrix adaptation evolution strategy (MO-CMA-ES), Non-dominated Sorting Genetic Algorithm-II (NSGA-II), SMetric Selection Evolutionary Multi-Objective Algorithm (SMS-EMOA) and Steady-State Multi-Objective Covariance Matrix Adaptation Evolution Strategy (SS-MO-CMA-ES). Obtained results show that the employed method possesses the capability to generate Pareto-optimal solutions of the formulated multi-objective optimization problems, whereas, the convexity of the Pareto front cannot be guaranteed. In addition, our results show that in terms of the convergence speed, the NSGA-II slightly outperforms the other three employed multi-objective optimization methods.