Under-frequency load shedding (UFLS) schemes are the latest safety measures applied for safeguarding the integrity of the grid against abrupt frequency imbalances. The overall inertia of electrical power systems is expected to decrease with an increased penetration of renewable energy as well as elements connected through power electronic interfaces. However, voltage source converter-based high voltage direct current (VSC-HVDC) links can provide virtual inertia through a control loop that allows for a reaction to occur at certain frequency fluctuations. This paper evaluates a UFLS scheme that considers the injection of virtual inertia through a VSC-HVDC link. A genetic algorithm (GA) is used to determine the location of the UFLS relays, the activation threshold of each stage, the delay time and the percentage of load shedding at each stage. It was found that the virtual inertia causes the nadir to delay and sometimes reach a greater depth. Furthermore, the implemented GA approximates the frequency response to the limits set with the constraints, reducing the load shedding but achieving a steeper nadir and a lower steady-state frequency level than traditional UFLS. The simulations were performed using the IEEE 39-bus test system.