Hybrid of the scatter search, improved adaptive genetic, and expectation maximization algorithms for phase-type distribution fitting

Although a large number of different methods for establishing the fitting parameters of PH distributions to data traces (PH fitting) have been developed, most of these approaches lack efficiency and numerical stability. In the present paper, a restricted class of PH distribution, called the hyper-Erlang distribution (HErD), is used to establish a maximum likelihood estimation model for data tracing. To fit the parameters, a hybrid algorithm based on the scatter search algorithm, the improved adaptive genetic algorithm, and the expectation maximization algorithm was developed to obtain the SS&IAGA-EM algorithm, which has a polynomial time complexity. In the data tracing tests for different distribution functions, the results obtained from SS&IAGA-EM and from the G-FIT, which is currently the best software for PH fitting, were compared. The present paper demonstrates that (a) the fitting effect of G-FIT does not positively correlate with the number of states of a HErD; thus, G-FIT repeatedly has to test the number of states manually to achieve a satisfactory fitting effect; (b) although setting range of the number of branches in G-FIT could mitigate the aforementioned deficiency, the combinations of the number of phases per branch grow exponentially; and (c) on SS&IAGA-EM can optimize the number of states and the number of phases automatically, aside from being slightly faster than G-FIT for a small number of branches and is significantly faster for a large number of branches. Moreover, in all tests, SS&IAGA-EM can achieve the same fitting quality as G-FIT for the same number of states.