Frequency regulation is in a first line of preference for an interconnected power system. Presence of nonlinearities in the generation systems further raises the complexity level of the problem. In this scenario, this article presents a robust Automatic Generation Control (AGC) mechanism to maintain the frequency and tie-line power of the power system to their nominal values. A Coefficient Diagram Method (CDM) based AGC mechanism including an AC/DC tie-line and Unified Power Flow Controller (UPFC) has been developed and the performance in handling the frequency regulation has been analyzed. The nonlinearities such as Governor Dead-Band (GDB) and Generation Rate Constraint (GRC) are included in the system to analyze the proposed AGC scheme in a more realistic approach. The AC/DC tie-line and UPFC which are included in the proposed AGC scheme provides an immense strength to handle the active power variation as-well-as frequency regulation. To develop a more effective AGC scheme, the parameters of an AC/DC tie-line and UPFC are optimized by successful implementation of the Fruit Fly Optimization Algorithm (FOA). The justification of the proposed AGC scheme has been carried out through a step by step verification such as justifying the CDM based controller, effectiveness of the proposed scheme and robustness of the system against parameters variation. The CDM based controller has been compared with the conventional controllers to elevate the effectiveness and the supremacy of the proposed AGC scheme has been examined by comparing with previously published work. The design and simulation of the work has been carried out by the MATLAB/Simulink® tool box.